BFS란?
BFS(Breadth-First Search, 너비 우선 탐색)는 그래프나 트리에서 가까운 노드부터 차례대로 탐색하는 알고리즘입니다. 시작 노드에서 한 단계씩 멀어지며 모든 노드를 방문합니다.
물에 돌을 던졌을 때 파문이 동심원으로 퍼져나가는 것처럼, BFS는 시작점에서 거리 1인 노드 → 거리 2인 노드 → 거리 3인 노드 순서로 탐색합니다.
왜 중요한가?
BFS는 그래프 알고리즘의 기본이며, 코딩 테스트에서 매우 자주 출제됩니다.
- •최단 경로 보장: 가중치가 없는 그래프에서 최단 경로를 찾을 수 있음
- •레벨별 탐색: 트리의 레벨 순회, 네트워크 계층 탐색에 활용
- •코딩 테스트 필수: 미로 탐색, 토마토 익히기, 최소 이동 횟수 등 대표 문제 다수
동작 원리
BFS는 큐(Queue) 자료구조를 사용합니다.
1단계. 시작 노드를 큐에 넣고 방문 표시합니다.
2단계. 큐에서 노드를 하나 꺼냅니다.
3단계. 꺼낸 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문 표시합니다.
4단계. 큐가 빌 때까지 2~3단계를 반복합니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(V + E) |
| 공간 | O(V) |
V는 정점(노드) 수, E는 간선 수입니다. 모든 노드를 한 번씩 방문하고, 모든 간선을 한 번씩 확인하므로 O(V + E)입니다.
BFS vs DFS 차이점
| 비교 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 (Queue) | 스택 (Stack) / 재귀 |
| 탐색 순서 | 가까운 노드 우선 | 깊은 노드 우선 |
| 최단 경로 | 보장 (가중치 없는 그래프) | 보장하지 않음 |
| 메모리 | 넓은 그래프에서 많이 사용 | 깊은 그래프에서 많이 사용 |
| 주요 활용 | 최단 거리, 레벨 순회 | 경로 탐색, 사이클 검출 |
최단 경로가 필요하면 BFS, 모든 경로를 탐색해야 하면 DFS를 선택합니다.
대표적인 활용 문제
미로 탐색 — 출발점에서 도착점까지 최소 이동 횟수를 구하는 문제. BFS로 풀면 처음 도착점에 도달한 순간이 최단 경로입니다.
토마토 익히기 — 여러 시작점에서 동시에 BFS를 수행하는 다중 시작점 BFS. 큐에 모든 시작점을 먼저 넣고 시작합니다.
네트워크 연결 확인 — 두 노드가 같은 네트워크에 속하는지 판별합니다.
자주 하는 실수
- •방문 체크를 큐에 넣을 때 하지 않고 꺼낼 때 하면 같은 노드가 여러 번 큐에 들어감
- •2차원 배열 문제에서 범위 체크를 누락하여 인덱스 초과
- •다중 시작점 BFS에서 시작점을 하나만 넣는 실수
알고노트에서 직접 확인하세요
BFS가 그래프에서 어떻게 파문처럼 퍼져나가는지, 알고노트에서 한 단계씩 시각적으로 확인할 수 있습니다. 노드와 간선을 직접 구성하고 탐색 과정을 관찰해보세요.