[백준] 경쟁적 전염 18405 (Python)

문제 링크

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

나의 풀이

1. 입력을 받으면서 초반 virus들의 정보를 [virus_num, 0(time), x, y] 별도의 list에 저장한다.
2. virus_num이 낮은 것들부터 전염이 되기 때문에 위 list를 정렬한다.
3. virus정보들을 담은 list를 q로 만든다.
4. time이 끝날 때까지 bfs알고리즘을 수행한다.

Code

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

from collections import deque

n, k = map(int,input().split())

graph = []
virus_info = []

for i in range(n):
    graph.append(list(map(int,input().split())))
    for j in range(n):
        if graph[i][j] != 0:
            virus_info.append((graph[i][j], 0, i, j))

s, end_x, end_y = map(int,input().split())

virus_info.sort()

q = deque(virus_info)

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

while q:
    virus_num, time, x, y = q.popleft()
    if time == s:
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and ny >= 0 and ny < n and graph[nx][ny] == 0:
            graph[nx][ny] = virus_num
            q.append((virus_num, time + 1, nx, ny))

print(graph[end_x-1][end_y-1])

Git

https://github.com/youngh0/Algorithm/blob/master/DFS%2CBFS/boj_18405.py