BFS vs DFS: 동작 방식·복잡도 비교와 문제 유형별 선택 기준
이 글의 핵심
그래프 문제를 만나면 BFS와 DFS 중 무엇을 써야 할지부터 막히기 쉽습니다. 둘 다 O(V+E)지만 BFS는 넓은 그래프에서 큐가 커지고, DFS는 깊은 그래프에서 재귀 한도에 걸립니다. 비교표와 BFS·재귀 DFS·반복 DFS 템플릿, 문제 유형별 선택 플로우차트로 판단 기준을 정리합니다.
들어가며
“BFS와 DFS 중 무엇을 써야 할까요?” 그래프 문제를 풀 때 가장 많이 하는 질문입니다. 이 글에서는 BFS와 DFS의 차이를 명확히 이해하며, 문제 유형에 맞는 알고리즘을 선택하는 방법을 다룹니다. 비유로 말씀드리면, BFS는 같은 거리(층)를 먼저 모두 확인하는 엘리베이터 안내에 가깝으며, DFS는 한 갈래를 끝까지 따라간 뒤 되돌아오는 미로·백트래킹에 가깝습니다. 최단 거리가 중요하면 층별로 퍼지는 쪽(BFS), 모든 분기를 깊게 시험해야 하면 한 줄기씩 파는 쪽(DFS)이 자연스럽습니다. BFS와 DFS 각각의 기초 구현을 Python으로 단계별로 따라가는 설명은 BFS와 DFS 입문 글에 있고, 이 글은 C++ 코드로 두 탐색을 나란히 놓고 “어떤 문제에서 어느 쪽을 고르고, 고른 뒤 어디서 틀리기 쉬운가”에 집중합니다.
BFS와 DFS 한눈에 비교
| 특성 | BFS | DFS |
|---|---|---|
| 자료구조 | 큐 (Queue) | 스택 (Stack) 또는 재귀 |
| 탐색 순서 | 레벨 순서 (가까운 것부터) | 깊이 우선 (끝까지) |
| 최단 경로 | ✅ 보장 (가중치 없는 그래프) | ❌ 보장 안 됨 |
| 메모리 | O(w) (너비) | O(h) (깊이) |
| 구현 | 반복문 | 재귀 또는 반복문 |
| 용도 | 최단 경로, 레벨 탐색 | 사이클 탐지, 경로 존재 |
성능·사용성·적용 시나리오 (한눈에)
| 구분 | BFS | DFS |
|---|---|---|
| 성능(시간) | 그래프 전체를 한 번씩 도는 점에서는 DFS와 동일하게 O(V+E) 수준 | 동일 |
| 성능(공간) | 큐에 한 레벨 분량이 몰릴 수 있어 넓은 그래프에서 부담 | 재귀 스택 또는 명시적 스택 깊이만큼. 매우 깊은 그래프에서는 스택 한계에 유의 |
| 사용성 | 거리·레벨 개념이 코드에 직접 드러나 최단 거리 문제에 직관적 | 재귀 한 방에 들어가기 쉬워 백트래킹·연결 요소에 편함 |
| 적용 시나리오 | 가중치 없는 최단 경로, 이분 그래프 판별, 레벨 순회 | 위상 정렬, 사이클·강한 연결 요소, “모든 경우” 탐색 |
언제 BFS를, 언제 DFS를 쓰나요?
- BFS를 고려하시면 좋은 경우: 시작점에서의 최소 이동 횟수·최소 간선 수가 필요하실 때, 또는 가까운 정점부터 차례로 처리해야 할 때입니다.
- DFS를 고려하시면 좋은 경우: 최단 거리보다 도달 가능 여부, 모든 경로·조합, 트리/그래프의 구조적 성질(사이클, 위상 순서)이 핵심일 때입니다.
- 둘 다 가능한 문제에서는 구현 난이도와 메모리 제한(넓은 그래프면 DFS 쪽이 유리할 수 있음)을 함께 보시면 됩니다.
큐와 재귀 호출이 만드는 방문 순서의 차이
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);
}
}
}
}이 코드에서 가장 중요한 한 줄은 visited[v] = true를 큐에 넣는 순간 한다는 점입니다. 꺼낼 때 표시하도록 바꿔도 방문 순서는 비슷해 보이지만, 아직 꺼내지 않은 정점이 여러 이웃에게서 중복으로 큐에 들어갑니다. 격자 문제에서는 한 칸이 최대 4번까지 들어갈 수 있고, 촘촘한 그래프에서는 큐 크기가 V가 아니라 E에 비례하게 불어나 “메모리 초과”나 시간 초과로 이어집니다. 코드가 틀린 답을 내지는 않기 때문에 작은 예제로는 발견되지 않고, 큰 입력에서만 터지는 전형적인 실수입니다.
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);
}
}
}둘 다 O(V+E)인데 메모리 사용량이 갈리는 이유
시간 복잡도
둘 다 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) | 비슷 |
표의 “O(V+E)“는 그래프를 인접 리스트로 저장했을 때의 복잡도입니다. 인접 행렬로 저장하면 정점마다 V개의 칸을 모두 확인해야 하므로 두 탐색 모두 O(V²)가 됩니다. 정점이 10만 개인 문제에서 인접 행렬을 만들면 탐색 이전에 메모리(10만×10만 칸)부터 감당할 수 없으므로, 코딩 테스트에서는 특별한 이유가 없으면 인접 리스트를 쓰는 것이 기본입니다.
메모리 표에서 실무적으로 더 중요한 것은 어떤 메모리가 한계에 걸리느냐입니다. BFS의 큐와 반복 DFS의 스택은 힙에 할당되므로 수백만 원소도 문제없이 담을 수 있지만, 재귀 DFS는 함수 호출 스택을 쓰기 때문에 기본 스택 크기(Linux 8MB, Windows 1MB가 흔함)에 묶입니다. 그래서 같은 O(h)라도 재귀 DFS는 깊이가 수십만이 되는 선형 그래프에서 세그멘테이션 폴트(스택 오버플로)로 죽을 수 있습니다. 채점 결과가 “런타임 에러”인데 로직에는 문제가 없어 보인다면 이 경우를 가장 먼저 의심해 볼 만합니다.
최단 경로는 BFS, 경로 존재·조합 탐색은 DFS
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); // 후위 순서
}위 두 DFS 코드는 그대로 쓰면 틀리기 쉬운 부분이 있습니다. hasCycle(u, parent)는 무방향 그래프 전용입니다. “방문한 이웃이 부모가 아니면 사이클”이라는 판단은 간선을 양방향으로 저장한 무방향 그래프에서만 성립하고, 방향 그래프에 적용하면 서로 다른 경로로 같은 정점에 도달했을 뿐인 경우(사이클이 아닌 DAG)도 사이클로 오판합니다. 방향 그래프에서는 정점을 “미방문 / 현재 재귀 스택에 있음 / 처리 완료” 세 가지 상태로 나누고, 현재 스택에 있는 정점을 다시 만났을 때만 사이클로 판단해야 합니다. 또 무방향 그래프라도 두 정점 사이에 간선이 두 개 있는 다중 간선 입력에서는 부모 정점 비교만으로는 그 사이클을 놓치므로, 부모 정점 대신 들어온 간선 번호를 기억하는 방식이 필요합니다.
topologicalSort는 후위 순서로 result에 쌓기 때문에 모든 정점을 처리한 뒤 result를 뒤집어야 위상 순서가 됩니다. 뒤집는 것을 잊으면 정반대 순서가 나오는데, 작은 예제에서는 우연히 맞아 보일 수 있어 놓치기 쉽습니다. 또 그래프가 여러 조각으로 나뉘어 있을 수 있으므로 한 정점에서만 호출하지 말고 모든 미방문 정점에서 호출해야 하며, 입력에 사이클이 있으면 이 코드는 에러 없이 잘못된 순서를 반환합니다. 사이클 검출까지 필요하면 진입 차수를 이용한 BFS 방식(Kahn 알고리즘)이 편한데, 큐에서 꺼낸 정점 수가 V보다 적으면 사이클이 있다는 뜻이라 판별이 간단합니다. 위상 정렬이 DFS 전용이 아니라는 점에서 선택표의 “위상 정렬 → DFS”는 여러 선택지 중 하나로 이해하면 됩니다.
바로 가져다 쓰는 BFS·DFS 템플릿
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);
}
}
}
}반복 DFS는 BFS와 반대로 꺼낼 때 방문 표시를 합니다. 넣을 때 표시하면 스택에 먼저 들어간 이웃이 나중에 다른 경로로 더 깊이 도달했을 때 건너뛰게 되어, 방문 순서가 재귀 DFS와 달라집니다(연결 요소를 세는 용도라면 상관없지만, 방문 순서나 발견·종료 시각이 의미 있는 위상 정렬·단절점 문제에서는 틀린 답이 됩니다). 대신 이 방식은 같은 정점이 스택에 여러 번 들어갈 수 있어 스택 크기가 최악 O(E)입니다. 정점마다 “다음에 볼 이웃 인덱스”를 함께 저장하는 stack<pair<int,int>> 방식으로 바꾸면 재귀와 똑같은 순서와 O(V) 스택을 동시에 얻을 수 있지만 코드가 길어지므로, 순서가 중요하지 않은 문제에서는 위 템플릿이면 충분합니다.
미로 탈출과 섬의 개수로 비교하기
미로 탈출: 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; // 경로 없음
}섬의 개수: 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;
}두 예제는 방문 표시 방식이 다릅니다. 미로 예제는 별도의 visited 배열을 두고, 섬 예제는 grid[x][y] = 0으로 입력 격자를 직접 지워 가며 방문을 표시합니다. 입력을 지우는 쪽은 메모리를 아끼고 코드가 짧지만, 함수가 호출자의 데이터를 망가뜨리므로 같은 격자를 다시 써야 하는 상황에서는 버그가 됩니다. 또 섬 예제의 재귀 DFS는 격자가 1000×1000이고 전부 육지일 때 재귀 깊이가 최대 수십만까지 갈 수 있어, 앞에서 말한 스택 한계에 걸립니다. 저는 격자 크기가 수백 이상인 문제에서는 연결 요소를 셀 때도 처음부터 BFS로 쓰는 편인데, 결과와 복잡도는 같으면서 스택 걱정이 없기 때문입니다.
미로 예제에서 BFS가 최단 거리를 보장하는 근거도 짚어 두겠습니다. 큐는 항상 “거리 d인 칸들 다음에 거리 d+1인 칸들”이 오는 순서를 유지하므로, 도착 칸을 처음 꺼낸 순간의 거리가 가능한 최솟값입니다. 이 성질은 모든 간선의 비용이 같을 때만 성립합니다. 칸마다 이동 비용이 다르면 Dijkstra를, 비용이 0 또는 1뿐이라면 비용 0인 이동은 덱의 앞에, 1인 이동은 뒤에 넣는 0-1 BFS를 쓰면 됩니다.
결정 플로우차트와 문제 유형별 선택표
플로우차트
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 | 레벨 구분 |
표의 “이유”는 어느 한쪽만 가능하다는 뜻이 아니라 구현이 자연스러운 쪽을 적은 것입니다. 이분 그래프 판별은 DFS로 번갈아 색을 칠해도 똑같이 풀리고, 연결 요소 개수는 BFS로도 같은 복잡도로 셀 수 있습니다. 진짜로 한쪽만 정답인 경우는 “가중치 없는 최단 거리”(BFS)와 “재귀 스택 상태를 이용하는 문제”(방향 그래프 사이클 검출, 단절점·강한 연결 요소 같은 DFS 트리 기반 알고리즘) 정도입니다. 나머지는 입력 크기와 재귀 깊이를 보고 안전한 쪽을 고르면 됩니다.
BFS·DFS 선택 요약
BFS와 DFS를 고르실 때의 핵심은 다음과 같습니다.
- 최단 경로(가중치 없음)가 필요하시면 → BFS가 맞습니다.
- 도달 여부·구조 탐색이 중심이면 → DFS가 다루기 쉬운 경우가 많습니다.
- 메모리는 그래프가 넓은지 깊은지에 따라 큐(BFS)와 스택(DFS) 부담이 달라지므로, 제한을 꼭 확인하시기 바랍니다.
- 구현 편의성은 문제 유형(백트래킹은 DFS 등)에 맞추시면 됩니다. 정리: 둘 다 시간은 O(V+E)로 같지만, 최단 거리가 문제의 정답 조건이면 BFS를 우선 검토하시는 것이 좋습니다.
FAQ
Q1. BFS가 항상 최단 경로를 보장하나요? 가중치가 없는 그래프에서만 보장됩니다. 가중치가 있으면 Dijkstra를 사용하세요.
Q2. DFS는 재귀로만 구현하나요? 스택을 사용한 반복문으로도 구현 가능합니다. 재귀가 더 간단하지만 스택 오버플로우 주의.
Q3. 둘 다 가능한 문제는 뭘 쓰나요? 구현하기 편한 것을 선택하면 됩니다. 시간 복잡도는 같으므로 성능 차이는 대개 미미하지만, 입력이 커서 재귀 깊이가 수만 이상으로 깊어질 수 있다면 재귀 DFS 대신 BFS나 반복 DFS를 고르는 것이 안전합니다.