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

문제

설명

매 초 바이러스가 인접한 칸으로 전염되고, 바이러스의 번호가 낮은 순부터 먼저 증식한다.

따라서 최소 힙을 구성하여 현재 바이러스의 시간과 번호를 차례로 넣어주면, 바이러스 중에서 시간이 가장 적은 바이러스가 먼저 선택되고, 같은 시간 내에서는 낮은 번호부터 선택된다.

풀이

import sys, heapq
input = sys.stdin.readline
DIR = [(1,0), (-1,0), (0,-1),(0,1)]

def bfs(graph, n, s):
    que = [] # (흐른 시간, 바이러스 레벨, y좌표, x좌표) 
    for i in range(n):
        for j in range(n):
            if graph[i][j] > 0:
                heapq.heappush(que, (0, graph[i][j], i, j))
    while que:
        t, _, y, x = heapq.heappop(que)
        for dx, dy in DIR:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and graph[ny][nx] == 0 and t < s:
                heapq.heappush(que, (t + 1, graph[y][x], ny, nx))
                graph[ny][nx] = graph[y][x]

    
def main():
    n, k = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(n)]
    s, x, y = map(int, input().split())
    bfs(graph, n, s)
    print(graph[x - 1][y - 1])
    
if __name__ == "__main__":
    main()