경쟁적 전염

풀이

 이 문제는 BFS를 이용해서 해결할 수 있다. 주의할 점은 각 바이러스가 낮은 번호부터 증식한다는 점이다. 낮은 번호부터 증식하므로 초기에 큐에 원소를 삽입할 때 낮은 바이러스의 번호부터 삽입해야 한다. 그래야 자연스럽게 오름차순으로 바이러스가 전염된다.

from collections import deque
N, K = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, input().split())))
S, X, Y = map(int, input().split())

# 초기 큐 설정
data = []
for i in range(N):
    for j in range(N):
        if graph[i][j] != 0:
            data.append((graph[i][j], i, j))
data.sort()
queue = deque(data)

# 동, 서, 남, 북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(queue):
    v, x, y = queue.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<N and 0<=ny<N and graph[nx][ny] == 0:
            graph[nx][ny] = v
            queue.append((v, nx, ny))

for i in range(S):
    for j in range(len(queue)):
        bfs(queue)

print(graph[X-1][Y-1])

시간 복잡도 : O(SN^2)