그래프 탐색의 기본: BFS와 DFS
그래프의 모든 정점을 방문하는 두 가지 기본 탐색 — 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS).
5/29/2026 · 5 min read
문제
그래프에서 한 정점에서 출발해 연결된 모든 정점을 빠짐없이 방문하고 싶다. 이때 "다음에 어떤 정점을 방문할지" 정하는 순서에 따라 두 가지 기본 전략이 나뉜다.
- BFS (너비 우선 탐색) — 가까운 정점부터, 같은 거리의 정점을 먼저 다 본다
- DFS (깊이 우선 탐색) — 한 방향으로 끝까지 들어갔다가 막히면 되돌아온다
둘 다 모든 정점·간선을 한 번씩 보므로 시간복잡도는 같지만, 방문 순서와 활용처가 다르다.
BFS — 너비 우선 탐색
정의BFS (Breadth-First Search)
시작 정점에서 가까운 정점부터 차례로 방문하는 탐색. **큐(queue)**를 사용하며, 가중치가 없는 그래프에서 최단 경로를 보장한다.
1
시작 정점을 큐에 넣고 방문 표시
시작 정점 를 큐에 push하고 방문 처리한다.
2
큐에서 하나 꺼내 처리
큐의 front를 꺼내 방문(출력 등)한다.
3
인접한 미방문 정점을 큐에 추가
꺼낸 정점의 이웃 중 아직 방문 안 한 정점을 큐에 넣고 즉시 방문 표시한다.
4
큐가 빌 때까지 반복
큐가 비면 도달 가능한 모든 정점을 방문한 것이다.
int N, M, C[1010]; // C: 방문 체크
vector<int> G[1010]; // 인접 리스트
void add_edge(int s, int e){ G[s].push_back(e); }
void BFS(int s){
queue<int> Q;
Q.push(s); C[s] = 1; // 시작 정점 방문 표시
while(!Q.empty()){
int v = Q.front(); Q.pop();
cout << v << " ";
// 이웃을 큐에 넣을 때 바로 방문 표시 → 중복 삽입 방지
for(auto i : G[v]) if(!C[i]) Q.push(i), C[i] = 1;
}
}큐에 넣는 시점에 방문 표시해야 한다. 꺼낼 때 표시하면 같은 정점이 큐에 여러 번 들어가 비효율적이거나 무한 루프가 생길 수 있다.
DFS — 깊이 우선 탐색
정의DFS (Depth-First Search)
한 방향으로 갈 수 있는 만큼 깊이 들어갔다가, 더 갈 곳이 없으면 직전 갈림길로 되돌아오는 탐색. **재귀(스택)**로 자연스럽게 구현된다.
int N, M, C[1010];
vector<int> G[1010];
void add_edge(int s, int e){ G[s].push_back(e); }
void DFS(int v){
cout << v << " ";
C[v] = 1; // 방문 표시
for(auto i : G[v]) if(!C[i]) DFS(i); // 미방문 이웃으로 재귀
}재귀 호출이 곧 "더 깊이 들어가는" 동작이고, 함수가 리턴되는 것이 "되돌아오는(backtrack)" 동작이다.
정점 수가 매우 많으면(수십만 이상) 재귀 DFS는 스택 오버플로가 날 수 있다. 그럴 땐 명시적인 stack을 써서 반복문으로 구현한다.
비교
| BFS | DFS | |
|---|---|---|
| 자료구조 | 큐 (queue) | 스택 / 재귀 |
| 방문 순서 | 가까운 것부터 | 깊은 곳부터 |
| 최단 경로 (무가중치) | ✅ 보장 | ❌ 보장 안 함 |
| 대표 활용 | 최단 거리, 레벨 탐색 | 사이클 검출, 위상 정렬, 연결 요소 |
TimeSpace
- 모든 정점()과 간선()을 한 번씩 보므로
- 방문 배열과 큐/재귀 스택에 공간
정리
- BFS: 큐, 가까운 것부터 → 무가중치 최단 경로
- DFS: 재귀/스택, 깊은 것부터 → 사이클·연결 요소·위상 정렬
- 둘 다 , 핵심은 방문 표시를 정확한 시점에 하는 것
기초 알고리즘인데 어렵다