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