[백준] 18405 경쟁적 전염 BFS 풀이

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

18405번: 경쟁적 전염

 

bfs에서 고려해야 할 점 

1. 1초에 한 칸 앞으로 이동할 수 있으며, 현재 몇 초가 경과했는지를 알아야 한다. -> '초' 에 대한 데이터를 어떻게 기록/ 갱신할 것인가 ?

2. 바이러스 숫자가 낮은 순으로 정렬되어야 한다 

이부분은 list에 바이러스 정보를 저장할 때 (virus, 시간, x좌표, y좌표)

로 저장해서 sort() 함수를 사용하면 맨 첫번째 virus 를 기준으로 오름차순 정렬이 된다.

그리고 이 list를 deque() 에 담아서 queue 자료 구조로 변환해 준다 !!!

-> 나는 여기서 heapq 라이브러리를 이용하여 우선순위 큐를 사용할 것을 떠올리게 되었다. 아무튼 queue를 사용하는 bfs가 더 유리하다고 판단되었다. 

 

문제를 푸는 핵심요소는 virus 정보를 저장하는 리스트에, 어떤 데이터를 담을것인가 ! 이다. 

bfs를 풀 때 보통 위치와 방문기록 정도만 있었다면, 이번에는 시간과 바이러스의 종류를 담아야 했다는 점이 기본 bfs 유형에서 응용해야 하는 것이다. 

 

# 18405 경쟁적 전염
from collections import deque

n, k = map(int, input().split())
graph = [] # 시험관의 정보 
virus = [] # virus 정보를 저장
for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        if graph[i][j] != 0:
            virus.append((graph[i][j], 0, i, j)) # virus, time, position_x, position_y

virus.sort()
q = deque(virus)

s, x, y = map(int, input().split())

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

def bfs():
    while q:
        v, t, x, y = q.popleft()
        if t == s:
            break 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = v
                    q.append((v, t+1, nx, ny))

bfs()
print(graph[x-1][y-1])

 

나머지 상하좌우 이동과 queue에 새롭게 이동한 지점 nx, ny를 enqueue 하는 것은 우리가 아는 BFS와 동일하다 

DFS/BFS 유형은 한번 이해를 해두면 응용해서 풀 수 있는 유형인 것 같다 ..!!