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

문제

18405번: 경쟁적 전염

입력

• 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력

• S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

입력 예제

3 3
1 0 2
0 0 0
3 0 0
2 3 2

3 3
1 0 2
0 0 0
3 0 0
1 2 2

출력 예제

3

0

문제 풀이

• 낮은 번호의 바이러스부터 증식하므로, 리스트를 만들어 그래프와 경과된 시간, 좌표를 넣어 정렬 후 큐에 삽입한다.
• 그 후 상하좌우 탐색을 진행하면서 바이러스를 증식시킨 후, s초가 경과했다면, 탐색을 멈춘다.
• s초가 경과한 후 그래프의 좌표값에 있는 바이러스를 출력한다.

코드

from collections import deque
dy = [-1,1,0,0]
dx = [0,0,-1,1]
n, k = map(int,input().split())
graph = []
data = []

# 낮은 번호 바이러스부터 큐에 넣기
for i in range(n):
    graph.append(list(map(int,input().split())))
    for j in range(n):
        if graph[i][j] != 0:
            data.append((graph[i][j],0,i,j))

data.sort()
queue = deque(data)
target_s, target_y, target_x = map(int,input().split())
while queue:
    virus, time, y, x = queue.popleft()
    if time == target_s:
        break
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < n and 0 <= nx < n and graph[ny][nx] == 0:
            graph[ny][nx] = virus
            queue.append((virus, time + 1, ny, nx))
print(graph[target_y -1][target_x - 1])