가까운 곳부터 층층이 퍼져 나가는 그래프 탐색(Breadth-First Search). 물에 돌을 던졌을 때 파문이 퍼지는 모양이다.
동작
1 거리 0
/ \
2 3 거리 1
/ \
4 5 거리 2
- 방문 순서: 1 → 2 → 3 → 4 → 5 — (거리 순)
구현 — 큐를 쓴다
Queue<Integer> q = new ArrayDeque<>();
q.offer(start);
visited[start] = true;
while (!q.isEmpty()) {
int node = q.poll();
for (int next : graph[node]) {
if (!visited[next]) {
visited[next] = true; // ★ 큐에 넣을 때 방문 표시
dist[next] = dist[node] + 1;
q.offer(next);
}
}
}
왜 큐인가 — "먼저 발견한 곳부터" 처리해야 거리 순으로 퍼진다. 그것이 FIFO다.
★ 표시 지점이 흔한 버그다. 꺼낼 때 방문 표시를 하면 같은 정점이 큐에 여러 번 들어가 메모리가 터지고 느려진다. 넣을 때 표시해야 한다.
BFS의 결정적 성질 — 최단 경로
간선 가중치가 모두 같으면(=1), BFS가 찾은 경로가 최단 경로다.
거리 1인 곳을 전부 본 뒤 거리 2로 넘어가므로, 처음 도달한 순간이 가장 짧은 경로임이 보장된다. DFS로는 이 보장이 없다.
가중치가 다르면 BFS로는 안 되고 다익스트라(우선순위 큐 사용)가 필요하다. 다익스트라는 "큐 대신 힙을 쓰는 BFS"라고 볼 수 있다.
DFS와의 선택
| DFS | BFS | |
|---|---|---|
| 자료구조 | 스택(재귀) | 큐 |
| 최단 경로 | ✗ | ○(가중치 동일 시) |
| 메모리 | O(깊이) | O(너비) — 층이 넓으면 큰 부담 |
| 유리한 경우 | 깊고 좁은 그래프, 모든 경우 탐색 | 답이 가까이 있을 때, 최단 거리 |
메모리 특성이 정반대다. 이진 트리 깊이 20이면 DFS는 20칸, BFS는 마지막 층 약 100만 칸을 큐에 담는다.
실무에서 어디에 있나
- 소셜 그래프의 "3촌 이내 친구" — 정확히 BFS의 층 개념
- 웹 크롤러 — 시작 URL에서 가까운 페이지부터 수집
- 네트워크 브로드캐스트·라우팅 홉 수
- 이미지 영역 채우기(flood fill)
- 캐시 워밍업 순서 결정 — 자주 함께 쓰이는 것부터 층별로
양방향 BFS
시작과 목표 양쪽에서 동시에 퍼뜨려 중간에서 만나게 한다.
- 단방향: 분기수^깊이 — = b^d 양방향: b^(d/2) + b^(d/2) = 2·b^(d/2) ← 지수가 절반
b=10, d=6이면 100만 → 2천. 500배 차이다.
목표 지점을 아는 경로 탐색에서 큰 효과를 낸다.