2026-01-19

멀티 소스 BFS (Multi-Source BFS) 정리

백준 17142번(연구소 3)을 풀면서
멀티 소스 BFS의 개념과 시간 계산 방식을 명확히 이해하게 되었다.

1. 멀티 소스 BFS란?

일반적인 BFS는 시작점이 하나이지만,
멀티 소스 BFS는 여러 개의 시작점을 동시에 큐에 넣고 탐색을 시작한다.

• 모든 시작점의 시작 시간은 동일하게 0
• BFS 특성상 가장 가까운 시작점에서 먼저 도달한 경로가 자동으로 선택됨
• 여러 출발지에서 동시에 퍼지는 상황을 정확히 모델링할 수 있음

2. 언제 멀티 소스 BFS를 써야 하는가?

다음 조건이 나오면 멀티 소스 BFS를 떠올릴 수 있다.

• 여러 개의 시작 지점이 동시에 출발
• “가장 먼저 도달한 시간”이 중요
• 각 시작점을 따로 BFS 돌리면 동시성 표현이 불가능한 경우

예)

• 여러 바이러스가 동시에 퍼짐
• 여러 불이 동시에 번짐
• 여러 사람/로봇이 동시에 이동

3. 17142번에서 멀티 소스 BFS가 필요한 이유

문제에서:

• 바이러스 후보(2) 중 M개를 선택
• 선택된 M개는 동시에 활성화
• 가장 빨리 도달한 바이러스 기준으로 시간이 결정됨

👉 이는
“여러 시작점에서 동시에 BFS”와 완전히 동일한 구조이다.

4. 멀티 소스 BFS 구현 핵심 코드

```python dist = [[-1] * n for _ in range(n)] q = deque()

for x, y in active_virus: dist[x][y] = 0 q.append((x, y))