백준 18405 경쟁적 전염 Python 풀이

유형 : DFS/BFS 

1. 바이러스의 종류는 1 ~ K 로, K 개이다. 

이 문제를 풀 때 바이러스가 상 하 좌 우 로 번식한다고 하니 

dfs / bfs로 이동하는걸 떠올렸다. 

그런데 나는 처음에 풀 때 dfs라고 생각했다 그런데 계속 재귀 호출 에러가 났다.

이 문제는 bfs로 풀어야 한다.

왜...? 왜일까 

bfs로 풀면 바이러스를 오름차순으로 정렬한다음에, 탐색할 수 있다 !!! 

풀이를 정리해 보면

1. graph 를 생성 !

정보를 받을 때 0초로 초기화 해서 저장한다. 이 문제의 특징은 s초가 지난 후의 x,y 좌표에 존재하는 바이러스 타입이 무엇인지 묻는 것이기 때문에 초 정보도 저장하는 것이 좋다.

2. 오름차순으로 바이러스 정렬

3. bfs 실행

# 경쟁적 전염
from collections import deque

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

graph = []
data = []
for i in range(n):
    graph.append(list(map(int, input().split())))

for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            data.append((graph[i][j],0,i,j)) # 바이러스 종류 - s - x - y

s, target_x, target_y = map(int, input().split())

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

data.sort()
q = deque(data)

while q:
    virus, time, x, y = q.popleft()
    if time == s:
        break
        
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

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

print(graph[target_x-1][target_y-1])