그래프 탐색 - DFS와 BFS - soo:bak

작성일 : 2025년 10월 25일

그래프 탐색이란?

그래프 탐색(Graph Traversal) 은 그래프의 모든 정점을 체계적으로 방문하는 과정을 의미합니다.

그래프는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조로,

소셜 네트워크, 지도의 경로, 웹 페이지 간 링크 등 다양한 실생활 문제를 모델링할 수 있습니다.

그래프 탐색이 필요한 이유는 다음과 같습니다:

연결성 확인: 두 정점 사이에 경로가 존재하는지 판단
최단 경로 탐색: 가장 짧은 경로를 찾아 이동 비용 최소화
네트워크 분석: 연결된 구성 요소나 영향력 있는 노드 파악
패턴 탐지: 특정 구조나 사이클 존재 여부 확인

그래프 탐색의 대표적인 두 가지 방법은 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 입니다.

이 두 방법은 정점을 방문하는 순서가 다르며, 각각 다른 특성과 장단점을 가지고 있습니다.

깊이 우선 탐색(DFS)

깊이 우선 탐색(Depth-First Search, DFS) 은 한 경로를 끝까지 탐색한 뒤 다른 경로로 넘어가는 방식입니다.

DFS의 원리

DFS는 시작 정점에서 출발하여 한 방향으로 갈 수 있는 가장 먼 정점까지 탐색한 뒤,

더 이상 방문할 정점이 없으면 이전 정점으로 돌아가(Backtracking) 다른 경로를 탐색하는 구조입니다.

이러한 방식은 스택(Stack) 또는 재귀 호출(Recursion) 을 통해 구현됩니다.

DFS의 동작 과정

다음과 같은 그래프에서 정점 1부터 DFS를 수행한다고 가정해봅시다:

DFS의 탐색 순서는 다음과 같습니다:

정점 1에서 시작
정점 1의 인접 정점 중 방문하지 않은 2로 이동
정점 2의 인접 정점 중 방문하지 않은 4로 이동
정점 4는 더 이상 방문할 인접 정점이 없으므로 2로 돌아감 (Backtrack)
정점 2도 더 이상 방문할 인접 정점이 없으므로 1로 돌아감
정점 1의 인접 정점 중 방문하지 않은 3으로 이동
정점 3의 인접 정점 중 방문하지 않은 5로 이동
정점 5는 더 이상 방문할 인접 정점이 없으므로 3으로 돌아감
정점 3의 인접 정점 중 방문하지 않은 6으로 이동
모든 정점 방문 완료

최종 방문 순서: 1 → 2 → 4 → 3 → 5 → 6

이처럼 DFS는 깊이를 우선으로 탐색하며, 막다른 곳에 도달하면 되돌아가는 방식으로 모든 정점을 방문합니다.

DFS의 구현

DFS는 재귀적 구조를 활용하면 간결하게 구현할 수 있습니다.

재귀를 이용한 구현

재귀 함수를 사용하는 방식이 가장 직관적이며 코드도 간결합니다.

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1001];  // 인접 리스트
bool visited[1001];      // 방문 여부 배열

void dfs(int v) {
  // 현재 정점을 방문 처리
  visited[v] = true;
  cout << v << " ";
  
  // 현재 정점의 모든 인접 정점을 탐색
  for (int next : adj[v]) {
    if (!visited[next]) {
      dfs(next);  // 방문하지 않은 정점에 대해 재귀 호출
    }
  }
}

재귀 호출을 사용하면 시스템 스택을 이용하여 자동으로 백트래킹이 이루어지므로,

별도의 스택 자료구조를 관리할 필요가 없습니다.

참고 : 백트래킹(Backtracking)의 개념과 구조적 사고 - soo:bak

장점:

코드가 간결하고 이해하기 쉬움
백트래킹이 자동으로 처리됨

단점:

재귀 깊이가 너무 깊으면 스택 오버플로우 발생 가능
함수 호출 오버헤드 존재

스택을 이용한 반복 구현

명시적으로 스택을 사용하여 반복문으로 구현할 수도 있습니다.

void dfs_iterative(int start) {
  stack<int> st;
  visited[start] = true;
  st.push(start);
  
  while (!st.empty()) {
    int v = st.top();
    st.pop();
    cout << v << " ";
    
    // 인접 정점을 스택에 추가
    for (int next : adj[v]) {
      if (!visited[next]) {
        visited[next] = true;
        st.push(next);
      }
    }
  }
}

스택을 명시적으로 사용하면 재귀 깊이 제한 문제를 피할 수 있습니다.

다만, 재귀 방식과는 탐색 순서가 약간 다를 수 있습니다.

너비 우선 탐색(BFS)

너비 우선 탐색(Breadth-First Search, BFS) 은 시작 정점에서 가까운 정점부터 차례대로 방문하는 방식입니다.

BFS의 원리

BFS는 시작 정점에서 인접한 모든 정점을 먼저 방문한 뒤,

그 다음 단계의 정점들을 순서대로 방문하는 구조입니다.

이러한 방식은 큐(Queue) 를 통해 구현되며, 레벨(Level) 단위로 탐색이 진행됩니다.

BFS의 동작 과정

앞서 DFS에서 사용한 동일한 그래프에서 정점 1부터 BFS를 수행해봅시다:

BFS의 탐색 순서는 다음과 같습니다:

레벨 0: 정점 1에서 시작 (거리 0)
레벨 1: 정점 1의 인접 정점인 2, 3을 큐에 추가 (거리 1)
레벨 2:
- 큐에서 2를 꺼내고, 2의 인접 정점인 4를 큐에 추가 (거리 2)
- 큐에서 3을 꺼내고, 3의 인접 정점인 5, 6을 큐에 추가 (거리 2)
레벨 3: 큐에서 4, 5, 6을 차례대로 처리
모든 정점 방문 완료

최종 방문 순서: 1 → 2 → 3 → 4 → 5 → 6

BFS는 너비(가까운 정점)를 우선으로 탐색하므로, 시작 정점으로부터의 최단 거리 순으로 정점을 방문합니다.

이는 가중치가 없는 그래프에서 최단 경로를 찾을 때 매우 유용합니다.

BFS의 구현

BFS는 큐 자료구조를 활용하여 구현합니다.

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1001];  // 인접 리스트
bool visited[1001];      // 방문 여부 배열

void bfs(int start) {
  queue<int> q;
  
  // 시작 정점을 방문 처리하고 큐에 추가
  visited[start] = true;
  q.push(start);
  
  while (!q.empty()) {
    // 큐에서 정점을 꺼냄
    int v = q.front();
    q.pop();
    cout << v << " ";
    
    // 현재 정점의 모든 인접 정점을 확인
    for (int next : adj[v]) {
      if (!visited[next]) {
        visited[next] = true;  // 방문 처리
        q.push(next);           // 큐에 추가
      }
    }
  }
}

최단 거리 계산

BFS는 가중치가 없는 그래프에서 최단 거리를 계산하는 데 활용됩니다.

vector<int> adj[1001];
int dist[1001];

void bfs_with_distance(int start) {
  queue<int> q;
  fill(dist, dist + 1001, -1);  // 거리를 -1로 초기화
  
  dist[start] = 0;
  q.push(start);
  
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    
    for (int next : adj[v]) {
      if (dist[next] == -1) {  // 아직 방문하지 않은 정점
        dist[next] = dist[v] + 1;  // 거리 갱신
        q.push(next);
      }
    }
  }
}

이 방식으로 각 정점까지의 최단 거리를 dist 배열에 저장할 수 있습니다.

DFS와 BFS 비교

DFS와 BFS는 모두 그래프의 모든 정점을 탐색하지만, 탐색 순서와 특성이 다릅니다.

주요 차이점

구분	DFS	BFS
탐색 방식	깊이 우선	너비 우선
자료구조	스택 / 재귀	큐
탐색 순서	한 경로를 끝까지 탐색	레벨 단위로 탐색
메모리 사용	상대적으로 적음	상대적으로 많음
최단 경로	보장 안 됨	보장됨 (가중치 없는 그래프)
구현 난이도	재귀로 간단	큐 사용
스택 오버플로우	재귀 깊이 제한 주의	발생하지 않음

메모리 사용 분석

DFS는 현재 탐색 중인 경로의 정점만 스택에 저장하므로,

최악의 경우 \(O(H)\) (\(H\)는 그래프의 최대 깊이)만큼의 메모리를 사용합니다.

BFS는 한 레벨의 모든 정점을 큐에 저장하므로,

최악의 경우 \(O(W)\) (\(W\)는 그래프의 최대 너비)만큼의 메모리를 사용합니다.

일반적으로 트리 구조에서는 너비가 깊이보다 크므로 BFS가 더 많은 메모리를 사용하지만,

그래프의 형태에 따라 달라질 수 있습니다.

시간 복잡도

DFS와 BFS 모두 그래프의 모든 정점과 간선을 한 번씩 방문하므로, 시간 복잡도는 동일합니다.

인접 리스트로 구현한 경우

\[O(V + E)\]

여기서 \(V\)는 정점의 개수, \(E\)는 간선의 개수입니다.

각 정점을 한 번씩 방문하는 데 \(O(V)\),

각 간선을 한 번씩 탐색하는 데 \(O(E)\)가 소요되므로 전체 시간 복잡도는 \(O(V + E)\)입니다.

일반적으로 그래프 문제에서는 인접 리스트를 사용하며, 이 경우 시간 복잡도가 효율적입니다.

인접 행렬로 구현한 경우

\[O(V^2)\]

인접 행렬을 사용하면 각 정점에 대해 모든 정점과의 연결 여부를 확인해야 하므로,

전체 시간 복잡도는 \(O(V^2)\)입니다.

이는 간선이 적은 희소 그래프(Sparse Graph) 에서는 비효율적이지만,

간선이 많은 밀집 그래프(Dense Graph) 에서는 인접 리스트와 비슷한 성능을 보입니다.

그래프 탐색의 활용

DFS와 BFS는 각각의 특성에 따라 다양한 문제에 활용됩니다.

DFS의 활용

1. 연결 요소 탐색

그래프에서 서로 연결된 정점들의 그룹을 찾는 문제입니다.

무방향 그래프에서 DFS를 수행하면, 한 번의 탐색으로 하나의 연결 요소를 찾을 수 있습니다.

예를 들어, 소셜 네트워크에서 친구 그룹을 찾거나,

지도에서 육지로 연결된 섬의 개수를 세는 문제에 활용됩니다.

2. 사이클 탐지

그래프 내에 사이클이 존재하는지 확인하는 문제입니다.

DFS를 수행하면서 이미 방문한 정점을 다시 만나면 사이클이 존재한다고 판단할 수 있습니다.

방향 그래프에서는 DFS 탐색 중인 경로 상의 정점을 다시 방문하는지 확인하고,

무방향 그래프에서는 부모 정점이 아닌 방문한 정점을 만나는지 확인합니다.

3. 위상 정렬

방향 비순환 그래프(DAG)에서 정점들의 선후 관계를 결정하는 문제입니다.

DFS를 수행하면서 정점을 완전히 탐색한 순서의 역순이 위상 정렬 결과가 됩니다.

이는 과목 선수 조건, 작업 의존성 등을 표현할 때 활용됩니다.

4. 경로 탐색

두 정점 사이에 경로가 존재하는지, 또는 모든 경로를 찾는 문제입니다.

DFS는 백트래킹과 결합하여 모든 가능한 경로를 탐색하거나,

특정 조건을 만족하는 경로를 찾는 데 효과적입니다.

BFS의 활용

1. 최단 경로 탐색

가중치가 없는 그래프에서 두 정점 사이의 최단 거리를 구하는 문제입니다.

BFS는 레벨 단위로 탐색하므로, 처음 도착한 경로가 항상 최단 경로입니다.

미로 탐색, 게임에서의 최소 이동 횟수, 네트워크에서의 최단 홉 수 등을 계산할 때 활용됩니다.

2. 단계별 탐색

시작점으로부터 거리별로 정점을 분류하는 문제입니다.

BFS는 자연스럽게 레벨 순서로 정점을 방문하므로, 각 단계별로 처리해야 하는 문제에 적합합니다.

예를 들어, 전염병 확산 시뮬레이션에서 며칠 차에 어느 지역이 감염되는지 계산하거나,

그래프에서 특정 거리 이내의 모든 정점을 찾는 문제에 활용됩니다.

3. 레벨 순회

트리를 레벨 단위로 순회하는 문제입니다.

BFS는 트리의 각 레벨을 순서대로 방문하므로, 레벨 순서 출력이나 레벨별 처리가 필요한 경우에 활용됩니다.

4. 연결 요소 탐색

DFS와 마찬가지로 BFS도 연결 요소를 찾는 데 사용할 수 있습니다.

DFS와 비교했을 때 탐색 순서만 다를 뿐, 결과는 동일합니다.

실전 예제: 연결 요소 개수 세기

그래프 탐색의 대표적인 활용 예제로, DFS를 사용하여 그래프의 연결 요소 개수를 구하는 문제를 살펴보겠습니다.

문제 설명

\(N\)개의 정점과 \(M\)개의 간선으로 이루어진 무방향 그래프가 주어질 때,

연결 요소의 개수를 구하는 프로그램을 작성하는 문제입니다.

연결 요소(Connected Component) 란 그래프에서 서로 연결된 정점들의 집합을 의미합니다.

접근 방법

방문하지 않은 정점을 찾습니다
해당 정점에서 DFS를 수행하여 연결된 모든 정점을 방문 처리합니다
연결 요소 개수를 1 증가시킵니다
모든 정점을 확인할 때까지 1~3 과정을 반복합니다

구현

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1001];  // 인접 리스트
bool visited[1001];      // 방문 여부 배열

// DFS 함수: v에서 시작하여 연결된 모든 정점을 방문
void dfs(int v) {
  visited[v] = true;
  
  for (int next : adj[v]) {
    if (!visited[next]) {
      dfs(next);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n, m;  // n: 정점의 개수, m: 간선의 개수
  cin >> n >> m;
  
  // 간선 정보 입력 (무방향 그래프)
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  int components = 0;  // 연결 요소 개수
  
  // 모든 정점에 대해 확인
  for (int i = 1; i <= n; i++) {
    if (!visited[i]) {  // 아직 방문하지 않은 정점이면
      dfs(i);            // 해당 정점에서 DFS 수행
      components++;      // 새로운 연결 요소 발견
    }
  }
  
  cout << components << "\n";
  
  return 0;
}

시간 복잡도 분석

모든 정점을 한 번씩 확인: \(O(V)\)
각 간선을 한 번씩 탐색: \(O(E)\)
전체 시간 복잡도: \(O(V + E)\)

마무리

DFS와 BFS는 그래프 탐색의 가장 기본적이면서도 중요한 알고리즘입니다.

DFS는 한 경로를 끝까지 탐색하는 방식으로 재귀적 구조를 활용하며,

백트래킹이 자연스럽게 이루어지므로 경로 탐색, 사이클 탐지, 위상 정렬 등의 문제에 적합합니다.

BFS는 가까운 정점부터 차례대로 방문하는 방식으로 큐를 활용하며,

레벨 단위 탐색이 자연스럽게 이루어지므로 최단 경로 탐색, 단계별 처리 등의 문제에 적합합니다.

두 알고리즘 모두 시간 복잡도는 \(O(V + E)\)로 동일하지만, 탐색 순서와 활용 분야가 다릅니다.

문제의 특성을 파악하여 적절한 탐색 방법을 선택하는 것이 중요합니다.

알고리즘 선택 가이드

최단 경로를 찾아야 한다면: BFS 사용
모든 경로를 탐색해야 한다면: DFS 사용
백트래킹이 필요하다면: DFS 사용
레벨별 처리가 필요하다면: BFS 사용
메모리가 제한적이라면: DFS 사용 (재귀 깊이 주의)
재귀 깊이가 제한적이라면: BFS 사용 또는 스택 기반 DFS 사용

그래프 탐색은 많은 알고리즘 문제의 기초가 되므로,

DFS와 BFS의 원리와 구현을 잘 이해하고 다양한 문제에 적용해보는 연습이 중요합니다.

관련 글:

백트래킹(Backtracking)의 개념과 구조적 사고 - soo:bak

관련 문제: