🦠 백준 18405번:경쟁적전염 (BFS 활용)
🧐 문제 해석
- N*N 크기의 시험관 안에 K번까지의 바이러스가 속해 있다.
- 매초마다 바이러스는 동서남북으로 전파되며, 단 번호가 빠른 바이러스 부터 전파된다.
- 어떤칸에 이미 바이러스가 들어가 있다면 그곳은 다른 바이러스가 들어갈 수 없다.
🎯 목표:
S초가 지났을 때 특정 칸에 어떤 바이러스가 존재하는지 혹은 존재하지 않는다면 0을 출력하라.
🔍 핵심 아이디어
이 문제는 **정답(특정 칸에 있는 바이러스의 종류)**를 BFS로 찾는 그래프 탐색 문제이다.
✅ BFS 용도
- 바이러스 전파 시키기
🦠 번호가 빠른 바이러스 부터 전파해라 !
virus_list = []
for i in range(n):
for j in range(n):
if graph[i][j] != 0:
virus_list.append((graph[i][j], 0, i, j))
virus_list.sort()- 바이러스가 포함된 정보를 입력 받아 큐에 추가하려고 한다.
- 이 문제에서는 큐에 시간에 대한 정보를 담아 추가 했다.
- 또한 번호가 빠른 바이러스부터 출력하기 위해서 튜플에 가장 앞 원소로 추가하고 오름차순 정렬을 했다.
⁉️ S초 후에 특정칸에는 어떤 바이러스가 전파되어 있는가?
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 0 <= nx < n and 0 <= ny < n:
if graph[nx][ny] == 0:
graph[nx][ny] = virus
q.append((virus, time + 1, nx, ny))
- 큐에는 이미 바이러스 순서대로 추가가 되어 있기 때문에 이후에 새로 전파된 바이러스 또한 오름차순으로 추가 될 것이다
- 애초에 한번이라도 바이러스가 전파되었다면 graph[nx][ny]가 0일 수가 없기 때문에 방문 처리를 위한 배열은 따로 필요하지 않다.
- S초가 되면 전파를 멈춘다
💯 정답
import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
s, target_x, target_y = map(int, input().split())
# 바이러스 정보 (번호, 시간, x, y)
virus_list = []
for i in range(n):
for j in range(n):
if graph[i][j] != 0:
virus_list.append((graph[i][j], 0, i, j))
virus_list.sort()
q = deque(virus_list)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
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 0 <= nx < n and 0 <= 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])
💭 생각
✅ 결론 한 줄
이 문제는 여러 개의 시작점에서 동시에 BFS를 수행하며, 시간 흐름에 따라 우선순위(바이러스 번호)를 유지해야 하는 전형적인 "우선순위 + 시간 BFS" 시뮬레이션 문제다! 🧬
🔑 BFS란?
BFS는 DFS처럼 상태를 함수 인자로 계속 넘기지는 않아. 대신, **"변화 정보 자체를 큐에 넣는" 방법이 적용 되었던 문제이다.
즉, dfs 처럼 함수 인자 없이도 queue.append((virus, time+1, nx, ny))처럼 큐에 상태를 누적해서 "지금 어떤 시점에서 어떤 전염이 일어나는지"를 계속 상태를 추적할 수도 있다는 것을 알 수 있는 문제였다.
그리고 이 문제를 풀면서 또 하나 중요했던건 “우선순위 정렬”을 큐에 넣기 전에 한 번 하고, 그 이후엔 FIFO인 큐의 특성으로 인해 자연스럽게 BFS가 그 우선순위를 유지하면서 전파가 진행된다는 사실이었다.
정리하자면, BFS는 단순히 큐를 사용해서 넓게 퍼진다는 애매모호한 정의에서 시간의 흐름 = 큐의 흐름이고, 그 안에 있는 상태 정보(시간, 거리, 우선순위 등)를 함께 다뤄야 정확한 결과를 낼 수 있는 방식인 것 같다.
