둔필승총

https://www.acmicpc.net/problem/18405

[문제 풀이]

처음에 많이 헤맸었다. 먼저 BFS를 최대한 활용하려고 했었는데 사실 활용하려고 한 게 더 복잡하게 이끌어 간 것 같다. 

이 문제는 s라는 변수에 시간이 주어지고 그 시간때에 위치를 출력하면 되는 문제이기 때문에 BFS를 활용하기 보다는 s만큼 움직여주고 그때의 값을 출력해주는 것이 더 편했다. queue를 만들어줘서 바이러스가 작은 순으로 저장해주고 각각의 바이러스를 꺼내어 상하좌우를 탐색하였다. 

from collections import deque
n,k = map(int,input().split())
graph=[] # n*n
for i in range(n):
    graph.append(list(map(int,input().split())))
s,u,v = map(int,input().split())
# s초 뒤에 (u,v)에 존재하는 바이러스의 종류 출력 -> 밑에서 x,y를 사용해서 u,v로 바꿈
dx=[-1,1,0,0]
dy=[0,0,1,-1]
q=deque()
for a in range(1,k+1):
    for i in range(n):
        for j in range(n):
            if graph[i][j]==a:
                q.append((i,j))
# print(q.popleft())
for _ in range(s):
    for _ in range(len(q)):
        x,y=q.popleft()
        num = graph[x][y]
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<n and graph[nx][ny]==0:
                graph[nx][ny]=num
                q.append((nx,ny))
print(graph[u-1][v-1])