알고리즘 BFS vs DFS 완벽 비교 | 그래프 탐색 선택 가이드
이 글의 핵심
BFS vs DFS 완벽 비교 - 동작 원리, 복잡도, 실전 선택 기준
들어가며
“BFS와 DFS 중 무엇을 써야 할까요?” 그래프 문제를 풀 때 가장 많이 하는 질문입니다. 이 글에서는 BFS와 DFS의 차이를 명확히 이해하고, 문제 유형에 맞는 알고리즘을 선택하는 방법을 다룹니다.
비유로 말씀드리면, BFS는 같은 거리(층)를 먼저 모두 확인하는 엘리베이터 안내에 가깝고, DFS는 한 갈래를 끝까지 따라간 뒤 되돌아오는 미로·백트래킹에 가깝습니다. 최단 거리가 중요하면 층별로 퍼지는 쪽(BFS), 모든 분기를 깊게 시험해야 하면 한 줄기씩 파는 쪽(DFS)이 자연스럽습니다.
이 글을 읽으면
- BFS와 DFS의 동작 원리를 이해하실 수 있습니다
- 시간·공간 복잡도 차이를 비교하실 수 있습니다
- 최단 경로, 사이클 탐지 등 문제 유형별 선택 기준을 익히실 수 있습니다
- 실전 구현 코드의 흐름을 따라가실 수 있습니다
목차
1. 빠른 비교표
| 특성 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 (Queue) | 스택 (Stack) 또는 재귀 |
| 탐색 순서 | 레벨 순서 (가까운 것부터) | 깊이 우선 (끝까지) |
| 최단 경로 | ✅ 보장 (가중치 없는 그래프) | ❌ 보장 안 됨 |
| 메모리 | O(w) (너비) | O(h) (깊이) |
| 구현 | 반복문 | 재귀 또는 반복문 |
| 용도 | 최단 경로, 레벨 탐색 | 사이클 탐지, 경로 존재 |
성능·사용성·적용 시나리오 (한눈에)
| 구분 | BFS | DFS |
|---|---|---|
| 성능(시간) | 그래프 전체를 한 번씩 도는 점에서는 DFS와 동일하게 O(V+E) 수준 | 동일 |
| 성능(공간) | 큐에 한 레벨 분량이 몰릴 수 있어 넓은 그래프에서 부담 | 재귀 스택 또는 명시적 스택 깊이만큼. 매우 깊은 그래프에서는 스택 한계에 유의 |
| 사용성 | 거리·레벨 개념이 코드에 직접 드러나 최단 거리 문제에 직관적 | 재귀 한 방에 들어가기 쉬워 백트래킹·연결 요소에 편함 |
| 적용 시나리오 | 가중치 없는 최단 경로, 이분 그래프 판별, 레벨 순회 | 위상 정렬, 사이클·강한 연결 요소, “모든 경우” 탐색 |
언제 BFS를, 언제 DFS를 쓰나요?
- BFS를 고려하시면 좋은 경우: 시작점에서의 최소 이동 횟수·최소 간선 수가 필요하실 때, 또는 가까운 정점부터 차례로 처리해야 할 때입니다.
- DFS를 고려하시면 좋은 경우: 최단 거리보다 도달 가능 여부, 모든 경로·조합, 트리/그래프의 구조적 성질(사이클, 위상 순서)이 핵심일 때입니다.
- 둘 다 가능한 문제에서는 구현 난이도와 메모리 제한(넓은 그래프면 DFS 쪽이 유리할 수 있음)을 함께 보시면 됩니다.
2. 동작 원리
BFS: 너비 우선 탐색
코드 흐름: 시작 정점을 큐에 넣고 visited로 표시한 뒤, 큐 앞에서 꺼낸 정점의 인접 정점을 아직 방문하지 않았으면 큐에 넣습니다. 이렇게 하면 가까운 거리부터 순서대로 방문합니다.
그래프:
1
/ \
2 3
/ \ \
4 5 6
BFS 순서: 1 → 2 → 3 → 4 → 5 → 6
(레벨 0) (레벨 1) (레벨 2)void BFS(int start) {
queue<int> q;
vector<bool> visited(n, false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
// 인접 정점 탐색
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}DFS: 깊이 우선 탐색
코드 흐름: 현재 정점을 방문 처리한 뒤, 인접 정점 중 미방문 정점으로 재귀적으로 먼저 들어갑니다. 한 줄기를 끝까지 간 뒤에야 다른 형제로 넘어가므로, BFS와 방문 순서가 달라집니다.
그래프:
1
/ \
2 3
/ \ \
4 5 6
DFS 순서: 1 → 2 → 4 → 5 → 3 → 6
(깊이 우선)void DFS(int u, vector<bool>& visited) {
visited[u] = true;
cout << u << " ";
for (int v : adj[u]) {
if (!visited[v]) {
DFS(v, visited);
}
}
}3. 시간/공간 복잡도
시간 복잡도
둘 다 O(V + E)
- V: 정점 수
- E: 간선 수
- 모든 정점과 간선을 한 번씩 방문
공간 복잡도
그래프 (완전 이진 트리):
1
/ \
2 3
/ \ / \
4 5 6 7
BFS 큐 최대 크기: 4 (마지막 레벨)
DFS 스택 최대 크기: 3 (트리 높이)BFS: O(w) - w는 그래프의 최대 너비
DFS: O(h) - h는 그래프의 최대 깊이
메모리 비교
| 그래프 형태 | BFS 메모리 | DFS 메모리 | 유리한 쪽 |
|---|---|---|---|
| 완전 이진 트리 (높이 h) | O(2^h) | O(h) | DFS |
| 선형 (1→2→3→…→n) | O(1) | O(n) | BFS |
| 일반 그래프 | O(V) | O(V) | 비슷 |
4. 문제 유형별 선택
BFS를 써야 하는 경우
-
최단 경로 (가중치 없는 그래프)
// 미로 탈출 최소 이동 횟수 int shortestPath(int start, int end) { queue<pair<int,int>> q; // {정점, 거리} q.push({start, 0}); visited[start] = true; while (!q.empty()) { auto [u, dist] = q.front(); q.pop(); if (u == end) return dist; // 최단 거리 보장 for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push({v, dist + 1}); } } } return -1; } -
레벨 순서 탐색
// 트리의 레벨별 출력 void levelOrder(TreeNode* root) { queue<TreeNode*> q; q.push(root); while (!q.empty()) { int levelSize = q.size(); for (int i = 0; i < levelSize; i++) { TreeNode* node = q.front(); q.pop(); cout << node->val << " "; if (node->left) q.push(node->left); if (node->right) q.push(node->right); } cout << "\n"; // 레벨 구분 } }
DFS를 써야 하는 경우
-
경로 존재 여부
// 경로가 있는지만 확인 (최단 경로 불필요) bool hasPath(int start, int end) { if (start == end) return true; visited[start] = true; for (int v : adj[start]) { if (!visited[v] && hasPath(v, end)) { return true; } } return false; } -
사이클 탐지
bool hasCycle(int u, int parent) { visited[u] = true; for (int v : adj[u]) { if (!visited[v]) { if (hasCycle(v, u)) return true; } else if (v != parent) { return true; // 사이클 발견 } } return false; } -
위상 정렬
void topologicalSort(int u) { visited[u] = true; for (int v : adj[u]) { if (!visited[v]) { topologicalSort(v); } } result.push_back(u); // 후위 순서 }
5. 구현 코드
BFS 템플릿
#include <queue>
#include <vector>
void BFS(int start) {
queue<int> q;
vector<bool> visited(n, false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
// 처리
process(u);
// 인접 정점
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}DFS 템플릿 (재귀)
void DFS(int u, vector<bool>& visited) {
visited[u] = true;
// 처리
process(u);
// 인접 정점
for (int v : adj[u]) {
if (!visited[v]) {
DFS(v, visited);
}
}
}DFS 템플릿 (반복)
#include <stack>
void DFS_iterative(int start) {
stack<int> stk;
vector<bool> visited(n, false);
stk.push(start);
while (!stk.empty()) {
int u = stk.top();
stk.pop();
if (visited[u]) continue;
visited[u] = true;
// 처리
process(u);
// 인접 정점 (역순으로 push하면 재귀와 같은 순서)
for (int i = adj[u].size() - 1; i >= 0; i--) {
int v = adj[u][i];
if (!visited[v]) {
stk.push(v);
}
}
}
}6. 실전 예제
예제 1: 미로 탈출 (BFS)
// 최단 경로 → BFS
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int shortestPath(vector<vector<int>>& maze) {
int n = maze.size(), m = maze[0].size();
queue<tuple<int,int,int>> q; // {x, y, 거리}
vector<vector<bool>> visited(n, vector<bool>(m, false));
q.push({0, 0, 0});
visited[0][0] = true;
while (!q.empty()) {
auto [x, y, dist] = q.front();
q.pop();
if (x == n-1 && y == m-1) return dist; // 도착
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
!visited[nx][ny] && maze[nx][ny] == 0) {
visited[nx][ny] = true;
q.push({nx, ny, dist + 1});
}
}
}
return -1; // 경로 없음
}예제 2: 섬의 개수 (DFS)
// 연결 요소 개수 → DFS
void DFS(vector<vector<int>>& grid, int x, int y) {
int n = grid.size(), m = grid[0].size();
if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
return;
}
grid[x][y] = 0; // 방문 표시
// 상하좌우 탐색
DFS(grid, x+1, y);
DFS(grid, x-1, y);
DFS(grid, x, y+1);
DFS(grid, x, y-1);
}
int numIslands(vector<vector<int>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
DFS(grid, i, j);
count++;
}
}
}
return count;
}7. 선택 기준 정리
플로우차트
graph TD
A[그래프 탐색 문제] --> B{최단 경로?}
B -->|Yes| C[BFS]
B -->|No| D{모든 경로 탐색?}
D -->|Yes| E[DFS]
D -->|No| F{메모리 제약?}
F -->|넓은 그래프| E
F -->|깊은 그래프| C
문제 유형별 선택표
| 문제 유형 | 알고리즘 | 이유 |
|---|---|---|
| 최단 경로 (가중치 없음) | BFS | 레벨 순서 보장 |
| 최단 경로 (가중치 있음) | Dijkstra | BFS 변형 |
| 경로 존재 여부 | DFS | 메모리 효율적 |
| 모든 경로 찾기 | DFS | 백트래킹 |
| 사이클 탐지 | DFS | 재귀 스택 활용 |
| 위상 정렬 | DFS | 후위 순서 |
| 연결 요소 개수 | DFS | 간단한 구현 |
| 이분 그래프 판별 | BFS | 레벨 구분 |
마무리
BFS와 DFS를 고르실 때의 핵심은 다음과 같습니다.
- 최단 경로(가중치 없음)가 필요하시면 → BFS가 맞습니다.
- 도달 여부·구조 탐색이 중심이면 → DFS가 다루기 쉬운 경우가 많습니다.
- 메모리는 그래프가 넓은지 깊은지에 따라 큐(BFS)와 스택(DFS) 부담이 달라지므로, 제한을 꼭 확인하시기 바랍니다.
- 구현 편의성은 문제 유형(백트래킹은 DFS 등)에 맞추시면 됩니다.
정리: 둘 다 시간은 O(V+E)로 같지만, 최단 거리가 문제의 정답 조건이면 BFS를 우선 검토하시는 것이 좋습니다.
FAQ
Q1. BFS가 항상 최단 경로를 보장하나요?
가중치가 없는 그래프에서만 보장됩니다. 가중치가 있으면 Dijkstra를 사용하세요.
Q2. DFS는 재귀로만 구현하나요?
스택을 사용한 반복문으로도 구현 가능합니다. 재귀가 더 간단하지만 스택 오버플로우 주의.
Q3. 둘 다 가능한 문제는 뭘 쓰나요?
구현하기 편한 것을 선택하세요. 성능 차이는 미미합니다.
관련 글
- 그래프 기초
- 최단 경로 알고리즘
- 위상 정렬
키워드
알고리즘, BFS, DFS, 그래프, 탐색, 최단 경로, 사이클, 위상 정렬, 비교, 선택 가이드