[백준-18405] 경쟁적 전염 / Python

18405번: 경쟁적 전염

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))
s, x, y = map(int, input().split())

queue = []
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            queue.append((graph[i][j], i, j, 0))

queue.sort()
queue = deque(queue)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while queue:
    virus, a, b, time = queue.popleft()
    if time == s:
        break
    for i in range(4):
        nx = a + dx[i]
        ny = b + dy[i]
        if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 0:
            graph[nx][ny] = virus
            queue.append((virus, nx, ny, time + 1))

print(graph[x - 1][y - 1])

 

해설

bfs로 해결했다. 주어진 시험관으로 0이 아닌 값을 찾아 큐에 넣고 정렬을 시켜준다.

1번 바이러스부터 탐색을 해주고 1번 바이러스의 상하좌우가 0이라면 1을 대입한다. 이를 2, 3번 바이러스에도 똑같이 적용한 후, 시간은 1초 늘어난다.

 

s와 늘어난 시간이 같아졌을 때, 반복문을 멈추고 구할 좌표의 값을 출력한다.