가중치 없는 그래프에서 최단 거리는 BFS와 DFS 중 무엇으로 구하나요?

가중치가 모두 같다면 BFS가 레벨 순으로 최단 경로를 줍니다. DFS는 최단 거리를 보장하지 않습니다.

DFS가 유리한 문제 유형은?

모든 경로 탐색·백트래킹·사이클 검출·위상 정렬의 일부 등 “깊게 들어갔다 나오기”가 자연스러운 경우에 자주 쓰입니다.

BFS의 공간 복잡도가 더 나쁜가요?

최악에는 큐에 한 레벨의 노드를 다 담아야 해서 넓은 그래프에서 메모리가 커질 수 있습니다. DFS는 스택 깊이에 따라 다릅니다.

visited 배열은 둘 다 필요한가요?

사이클이 있는 그래프에서는 일반적으로 방문 표시가 필요합니다. 트리처럼 방향이 명확하면 생략 가능한 경우도 있습니다.

알고리즘 BFS vs DFS 완벽 비교 | 그래프 탐색 선택 가이드

2026년 3월 30일 · 21분 읽기 · 수정 2026년 4월 7일 초급 가이드

이 글의 핵심

BFS와 DFS의 차이점을 동작 원리, 시간 복잡도, 공간 복잡도 관점에서 비교. 최단 경로, 사이클 탐지 등 실전에서 어떤 알고리즘을 써야 하는지 선택 기준을 설명합니다.

들어가며

“BFS와 DFS 중 무엇을 써야 할까요?” 그래프 문제를 풀 때 가장 많이 하는 질문입니다. 이 글에서는 BFS와 DFS의 차이를 명확히 이해하고, 문제 유형에 맞는 알고리즘을 선택하는 방법을 다룹니다. 비유로 말씀드리면, BFS는 같은 거리(층)를 먼저 모두 확인하는 엘리베이터 안내에 가깝고, DFS는 한 갈래를 끝까지 따라간 뒤 되돌아오는 미로·백트래킹에 가깝습니다. 최단 거리가 중요하면 층별로 퍼지는 쪽(BFS), 모든 분기를 깊게 시험해야 하면 한 줄기씩 파는 쪽(DFS)이 자연스럽습니다.

이 글을 읽으면

BFS와 DFS의 동작 원리를 이해하실 수 있습니다
시간·공간 복잡도 차이를 비교하실 수 있습니다
최단 경로, 사이클 탐지 등 문제 유형별 선택 기준을 익히실 수 있습니다
실전 구현 코드의 흐름을 따라가실 수 있습니다

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.

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)	비슷

일상 비유로 이해하기: 시간 복잡도는 책에서 원하는 페이지를 찾는 방법으로 비유할 수 있습니다. O(1)은 목차를 보고 바로 찾기, O(log n)은 이진 탐색처럼 중간을 펼쳐 앞뒤 판단하기, O(n)은 첫 페이지부터 하나씩 넘기기, O(n²)은 모든 페이지 조합을 확인하기입니다.

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, 그래프, 탐색, 최단 경로, 사이클, 위상 정렬, 비교, 선택 가이드

심화 부록: 구현·운영 관점

이 부록은 앞선 본문에서 다룬 주제(「알고리즘 BFS vs DFS 완벽 비교 | 그래프 탐색 선택 가이드」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.

내부 동작과 핵심 메커니즘

flowchart TD
  A[입력·요청·이벤트] --> B[파싱·검증·디코딩]
  B --> C[핵심 연산·상태 전이]
  C --> D[부작용: I/O·네트워크·동시성]
  D --> E[결과·관측·저장]

sequenceDiagram
  participant C as 클라이언트/호출자
  participant B as 경계(런타임·게이트웨이·프로세스)
  participant D as 의존성(API·DB·큐·파일)
  C->>B: 요청/이벤트
  B->>D: 조회·쓰기·RPC
  D-->>B: 지연·부분 실패·재시도 가능
  B-->>C: 응답 또는 오류(코드·상관 ID)

불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.

프로덕션 운영 패턴

영역	운영 관점 질문
관측성	요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가
안전성	입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가
신뢰성	재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가
성능	캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가
배포	롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가
용량	피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가

스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.

확장 예시: 엔드투엔드 미니 시나리오

앞선 본문 주제(「알고리즘 BFS vs DFS 완벽 비교 | 그래프 탐색 선택 가이드」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.

입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.

handle(request):
  ctx = newCorrelationId()
  validated = validateSchema(request)
  authorize(validated, ctx)
  result = domainCore(validated)
  persistOrEmit(result, idempotentKey)
  recordMetrics(ctx, latency, outcome)
  return result

문제 해결(Troubleshooting)

증상	가능 원인	조치
간헐적 실패	레이스, 타임아웃, 외부 의존성, DNS	최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검
성능 저하	N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스	프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거
메모리 증가	캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납	상한·TTL·힙/FD 스냅샷 비교
빌드·배포만 실패	환경 변수, 권한, 플랫폼 차이, lockfile	CI 로그와 로컬 diff, 런타임·이미지 버전 핀
설정 불일치	프로필·시크릿·기본값, 리전	스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화
데이터 불일치	비멱등 재시도, 부분 쓰기, 캐시 무효화 누락	멱등 키·아웃박스·트랜잭션 경계 재검토

권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.

배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

이 글에서 다루는 키워드 (관련 검색어)

알고리즘, BFS, DFS, 그래프, 탐색, 최단 경로, 비교 등으로 검색하시면 이 글이 도움이 됩니다.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.