[Baekjoon] 18405. 경쟁적 전염

🔗 Problem Link

18405번: 경쟁적 전염

---

❔Thinking

• NXN 시험관에 바이러스가 순서대로 상,하,좌,우로 퍼져나갈 때, S초 뒤에 X,Y에 존재하는 바이러스를 반환한다.
• 바이러스는 1~K까지 있고, 작은 순서대로 퍼져간다.

---

💻Solution

import heapq
import sys

input = sys.stdin.readline

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

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())

# 초기 바이러스 확인
q = []
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            heapq.heappush(q, (graph[i][j], i, j))

# 바이러스 감염
def virus_spread(graph, q):
    next_q = []
    while q:
        virus, x, y = heapq.heappop(q)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<len(graph) and 0<=ny<len(graph[0]) and graph[nx][ny] == 0:
                graph[nx][ny] = virus
                heapq.heappush(next_q, (virus, nx, ny))
    return graph, next_q

# s초 후 상태
for t in range(s):
    graph, q = virus_spread(graph, q)
    
print(graph[x-1][y-1])

---

🗝️keypoint

1. 바이러스가 작은 순서대로 퍼져나가므로, 그 순서를 유지하는 것이 중요하다.
2. 바이러스는 초당 상,하,좌,우 각 한 번씩만 퍼져나간다.