[BOJ 18405] 경쟁적 전염 (Python)

문제

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

18405번: 경쟁적 전염

 

풀이

최소힙으로 낮은 번호의 바이러스부터 증식시켰고, 

모든 증식이 끝난 후에 시간을 증가 시킨 후 다음 바이러스를 큐에 넣었다. 

다른 답안을 보니 virus를 소팅하고 deque를 이용해 정석적인 BFS 방식으로 풀 수 있었는데 좀 돌아서 간 것 같다.

소스코드

from collections import deque
import heapq

n, k = map(int, input().split())
arr = [[0]*(n+1) for _ in range(n+1)]
q = []
for i in range(1, n+1):
    data = list(map(int, input().split()))
    for j in range(1, n+1):
        arr[i][j] = data[j-1]
        if data[j-1] != 0:
            # virus
            heapq.heappush(q, (data[j-1], i, j))

# viruses.sort()
s, a, b = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

if s == 0:
    print(arr[a][b])
    exit(0)

time = 0
next_viruses = []
while len(q) > 0:
    t, x, y = heapq.heappop(q)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx <= 0 or ny <= 0 or nx > n or ny > n or arr[nx][ny] != 0:
            continue
        arr[nx][ny] = t
        next_viruses.append((t, nx, ny))

    if len(q) == 0:
        time += 1
        if time == s:
            print(arr[a][b])
            exit(0)
        for virus in next_viruses:
            heapq.heappush(q, virus)
        next_viruses = []

print(arr[a][b])
exit(0)