파이썬 백준 18405 경쟁적 전염

import sys
input = sys.stdin.readline
from collections import deque
 
n, k = map(int, input().split())
T = []
V = [[] for i in range(k + 1)]
T.append([None for i in range(n + 1)])
for i in range(1, n + 1) : 
    T.append([None] + list(map(int, input().split())))
    for j in range(1, n + 1) : 
        if T[i][j] > 0 : 
            V[T[i][j]].append([i, j])
 
s, X, Y = map(int, input().split())
 
que = deque()
for i in range(1, k + 1) : 
    for virus in V[i] : 
        que.append(virus)
que.append(['t', None])
 
t = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while que and t < s : 
    a, b = que.popleft()
    if a != 't' : 
        for i in range(4) : 
            x = a + dx[i]
            y = b + dy[i]
            if x <=n and y <= n and T[x][y] == 0 : 
                T[x][y] = T[a][b]
                que.append([x, y])
    else : 
        t = t + 1
        que.append(['t', None])
print(T[X][Y])

line 5 ~ 15

2차원 행렬 T를 인풋받은대로 만든다.

order가 작은 바이러스가 감염의 우선권이 있으므로, 큐에 order 순으로 담아야 한다.

order i의 바이러스의 좌표를 V[i]에 담는다.

 

line 17 ~ 21

V를 이용하여 order 순으로 바이러스를 큐에 담고, 마지막으로 매 순환마다 시간을 +1할 't'를 넣는다.

 

line 23 ~ 38

시간 t가 s가 되면 멈추는 while문으로 BFS를 구현한다.

큐에서 pop된 것이 바이러스의 좌표라면 인접 4방향의 0을 감염시키고 큐에 넣는다.

큐에 order 순으로 담았으므로 매 시간 order가 우선인 바이러스가 큐의 앞에서 처리되어 먼저 0을 감염시킨다.

pop된 것이 't'라면 이 시간에 감염가능한 모든 바이러스가 연산을 마친 것이므로 시간을 +1한다.

시간 s가 되어 while문이 종료되었을 때 요구받은 좌표 X, Y의 값을 출력한다.