[알고리즘] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

이 글은 가장 대표적인 그래프 탐색 방법인 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)에 대해 정리한 글입니다.

---

깊이 우선 탐색 (DFS)

깊이 우선 탐색(DFS, Depth First Search)은 그래프 탐색 알고리즘 중에서도 가장 기초적이고 중요한 알고리즘 중 하나로, 트리 구조 및 다양한 그래프 문제에서 폭넓게 활용된다.

DFS의 개념

정의

• DFS는 시작 정점에서부터 한 경로로 깊숙이 들어가며 탐색을 진행하다가, 더 이상 진행이 불가능해지면 바로 앞 단계로 되돌아와 다른 경로를 탐색하는 방식
• 재귀 또는 스택을 사용하여 구현

특징

• 그래프에서 한 정점에서 출발하면, 가능한 멀리까지(깊이) 진행
• 탐색 과정에서 한 번 방문한 정점은 보통 다시 방문하지 않도록 방문 배열(visited) 등을 사용
• 트리 구조(사이클이 없는 그래프)에서의 DFS는 간단히 모든 노드를 방문하는 순회 과정이 됨
• 사이클이 있는 그래프에서도, 방문했던 노드를 다시 방문하지 않도록 관리하면 중복 방문을 막을 수 있음 

응용

• 그래프의 모든 정점 방문 : 연결 요소 개수 확인, 경로 탐색 등
• 사이클 판별 : DFS 과정에서 이미 방문 중인 경로에 속한 노드를 다시 방문하면 사이클 존재
• 위상 정렬(Topological Sort), 백트래킹(Backtracking), 트리/그래프 동적 계획법 등
• 경로 생성

그래프 표현 방식

일반적으로 그래프를 표현(저장)하는 방식으로는 인접 리스트(Adjacency List) 방식과 인접 행렬(Adjacency Matrix) 방식을 사용한다. (최근 코딩테스트에서는 인접 리스트 방식을 더 많이 사용하는 경향이 있다.)

희소 그래프와 조밀 그래프
✅ 희소 그래프 : 전체 가능한 간선 수에 비해 실제 간선이 훨씬 적은 그래프를 의미
✅ 조밀 그래프 : 전체 가능한 간선 수에 비해 실제 간선이 많은 그래프를 의미

인접 리스트 방식

• 각 정점마다 연결된 다른 정점들을 리스트(또는 벡터 등) 형태로 저장
• 정점에 연결된 간선만 기록하므로, 희소 그래프(Sparse Graph)에서 메모리를 절약할 수 있음
• 특정 정점에 인접한 정점을 빠르게 조회할 수 있지만, 두 정점이 직접 연결되어 있는지 확인할 때는 해당 정점의 리스트를 순회해야 함

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 4;  // 정점 개수
    // 각 인덱스(정점)에 대해, 연결된 정점 정보를 저장할 벡터(리스트) 선언
    vector<vector<int>> adjList(n);

    // 간선 정보를 추가: (0 - 1), (1 - 2), (2 - 3), (3 - 0)
    // 무방향 그래프이므로 양방향으로 추가
    adjList[0].push_back(1);
    adjList[0].push_back(3);

    adjList[1].push_back(0);
    adjList[1].push_back(2);

    adjList[2].push_back(1);
    adjList[2].push_back(3);

    adjList[3].push_back(0);
    adjList[3].push_back(2);

    // 인접 리스트 출력
    for (int i = 0; i < n; i++) {
        cout << "정점 " << i << "에 인접한 정점: ";
        for (int neighbor : adjList[i]) {
            cout << neighbor << " ";
        }
        cout << endl;
    }

    return 0;
}

인접 행렬 방식

• 정점을 행과 열로 나타낸 2차원 배열(또는 벡터)을 사용해, 두 정점 간 연결 여부를 0 또는 1로 저장
• 모든 정점 쌍에 대한 정보를 담기 때문에, 조밀 그래프(Dense Graph)에서 유용함
• 두 정점이 연결되어 있는지를 인덱스로 바로 확인할 수 있지만, 정점 수가 $ n $ 개일 때 행렬의 크기가 $ n \times n $ 이 되므로 메모리 사용량이 커지게 됨

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 4;  
    // n x n 크기의 2차원 벡터를 0으로 초기화
    vector<vector<int>> adjMatrix(n, vector<int>(n, 0));

    // 간선 정보 등록: (0 - 1), (1 - 2), (2 - 3), (3 - 0)
    adjMatrix[0][1] = 1;  // 0번 정점과 1번 정점 연결
    adjMatrix[1][0] = 1;  // 무방향이므로 대칭

    adjMatrix[1][2] = 1;
    adjMatrix[2][1] = 1;

    adjMatrix[2][3] = 1;
    adjMatrix[3][2] = 1;

    adjMatrix[3][0] = 1;
    adjMatrix[0][3] = 1;

    // 인접 행렬 출력
    cout << "    ";
    for (int col = 0; col < n; col++) {
        cout << col << " ";
    }
    cout << endl;

    for (int row = 0; row < n; row++) {
        cout << row << " : ";
        for (int col = 0; col < n; col++) {
            cout << adjMatrix[row][col] << " ";
        }
        cout << endl;
    }

    return 0;
}

DFS 구현 방법

DFS를 구현할 때에는 재귀(recursive) 방식과 스택(stack) 방식으로 구현할 수 있다. 일반적으로 재귀 함수를 이용한 방식이 사용된다.

재귀를 사용한 DFS

• 함수 dfs(u)를 호출하면 정점 u를 방문 처리(visited[u] = true)하고, u와 인접한 모든 정점 v에 대해 방문하지 않은 정점이면 dfs(v)를 재귀 호출
• 재귀 호출 스택을 통해 자연스럽게 깊이 우선으로 탐색이 진행
• 코드가 간결하고 직관적이지만, 깊이가 매우 큰 그래프(트리) 등을 탐색하는 경우 스택 오버플로(stack overflow)가 발생할 수 있음

#include <iostream>
#include <vector>
using namespace std;

// 방문 여부 체크용 벡터(전역 또는 필요 시 main 내에서 관리해도 무방)
vector<bool> visited;
vector<vector<int>> adj;  // 인접 리스트

void dfsRecursive(int u) {
    // 현재 정점 u 방문 처리
    visited[u] = true;
    cout << u << " ";

    // u와 인접한 모든 정점을 확인
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfsRecursive(v);
        }
    }
}

int main() {
    int n = 4;  // 정점의 개수
    // n개의 벡터를 가진 2차원 벡터(인접 리스트) 초기화
    adj.assign(n, vector<int>());

    // 간선 정보 (무방향 그래프)
    // 0 - 1
    adj[0].push_back(1);
    adj[1].push_back(0);

    // 1 - 2
    adj[1].push_back(2);
    adj[2].push_back(1);

    // 2 - 3
    adj[2].push_back(3);
    adj[3].push_back(2);

    // 3 - 0
    adj[3].push_back(0);
    adj[0].push_back(3);

    // 방문 벡터 false로 초기화
    visited.assign(n, false);

    cout << "[재귀 DFS] 탐색 순서: ";
    dfsRecursive(0);  // 0번 정점부터 DFS 시작
    cout << endl;

    return 0;
}

스택을 사용한 DFS

• 스택 자료구조를 직접 사용하여, 재귀 호출 스택을 대체하는 방식
• 초기 정점을 스택에 넣고(push()) 스택이 빌 때까지 아래 과정을 반복
  • 스택의 맨 위(top()) 정점을 꺼낸 뒤(pop()), 아직 방문하지 않았다면 방문 처리
  • 해당 정점과 인접한 아직 방문하지 않은 정점들을 스택에 추가
• 사용자가 직접 스택을 관리하기 때문에 재귀 깊이에 대한 부담이 비교적 적지만 코드가 재귀 방식에 비해 길어질 수 있음
• 재귀 방식과 달리, 대규모 그래프(깊은 탐색)에 적합

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    int n = 4;  // 정점의 개수
    vector<vector<int>> adj(n);

    // 간선 정보 (무방향 그래프)
    // 0 - 1
    adj[0].push_back(1);
    adj[1].push_back(0);

    // 1 - 2
    adj[1].push_back(2);
    adj[2].push_back(1);

    // 2 - 3
    adj[2].push_back(3);
    adj[3].push_back(2);

    // 3 - 0
    adj[3].push_back(0);
    adj[0].push_back(3);

    // 방문 여부
    vector<bool> visited(n, false);

    cout << "[스택 DFS] 탐색 순서: ";

    // DFS를 위한 스택 준비
    stack<int> st;

    // 시작 정점(예: 0) 스택에 삽입
    st.push(0);

    // 스택이 빌 때까지 반복
    while (!st.empty()) {
        int u = st.top();
        st.pop();

        // 이미 방문한 정점이면 무시
        if (visited[u]) {
            continue;
        }

        // 방문 처리 및 출력
        visited[u] = true;
        cout << u << " ";

        // 인접한 정점들을 스택에 삽입
        // (스택 특성상, 뒤에 넣은 정점부터 먼저 탐색)
        // 순서 제어를 위해 인접 리스트를 역순 탐색하기도 함
        for (int v : adj[u]) {
            if (!visited[v]) {
                st.push(v);
            }
        }
    }

    cout << endl;

    return 0;
}

DFS의 시간 복잡도

• 인접 리스트 사용 시
  • 각 간선을 최대 두 번(무방향 그래프라면 양방향) 확인하고, 각 정점을 최대 한 번 방문
  • $ O(V + E) $ (단, $ V $ 는 정점 개수, $ E $ 는 간선 개수)
• 인접 행렬 사용 시
  • 모든 정점에 대해 인접 행렬을 조회하면, 가선 정보를 탐색할 때 $ O(V) $
  • 총 $ V $ 개 정점을 $ V $ 번 조회 > $ O(V^2) $

DFS 구현 시 주의사항

• 방문 배열 처리
  • 무방향 그래프든, 유향 그래프든, 방문 여부를 저장해야 무한 루프나 중복 방문을 피할수 있음 
• 스택 오버플로
  • 재귀 깊이가 너무 깊어지면 스택 오버플로 발생 가능 (특히 파이썬..)
  • 입력 크기가 매우 큰 그래프이면, 스택 방식 사용을 고려하는 것이 좋음
• 인접 리스트 정렬
  • 문제에서 "정점 번호가 작은 순서대로 탐색" 등을 요구하면, 인접 리스트를 정렬하거나 우선순위 큐를 사용
  • 기본적으로 DFS 순서는 구현 세부사항(리스트 순서)에 따라 달라질 수 있음
• 이방문(Visit Twice) 가능성
  • 특정 문제에서는 한 노드를 여러 번 방문해도 되는 경우가 있기 때문에 문제의 조건에 따라 설계를 달라질 수 있음
  • 일반적으로 그래프 기본 탐색에서는 한 번 방문한 노드는 다시 방문하지 않음

---

너비 우선 탐색 (BFS)

너비 우선 탐색(BFS, Breadth First Search)은 그래프 탐색 알고리즘에서 DFS와 함께 가장 기초적이면서도 특정 문제에 매우 자주 사용되는 알고리즘이다.

BFS의 개념

정의

• 그래프에서 시작 정점으로부터 가까운 정점(직접 연결된 정점)들을 먼저 방문하고, 그 다음으로 한 단계 더 떨어져 있는 정점들을 방문해 나가는 방식
• 루트(시작점)로부터 거리(간선 수)가 1인노드를 모두 방문한 뒤, 거리가 2인 노드, 그 다음 거리가 3인 노드 등으로 확장해 가며 탐색 

특징

• 일반적으로 큐(queue) 자료구조를 사용하여 구현
• 무가중치 그래프에서 최단 경로(간선 수가 최소) 탐색 시 사용
• 방문 순서가 레벨(거리) 단위로 진행되어, 일종의 계층적(level-order) 방문 형태를 가짐

응용

• 최단 거리 문제 : 가중치가 없는 그래프에서, 한 노드에서 다른 노드까지 최단 거리(간선 수)를 구할 때 사용
• 트리의 레벨 순회 : 이진 트리 또는 일반 트리에서 레벨 별 방문
• 그래프의 연결 여부, 최소 간선 수 등을 쉽게 파악할 수 있음

그래프 표현 방식

DFS와 마찬가지로 BFS에서도 인접 리스트 또는 인접 행렬로 그래프를 표현(저장)할 수 있다. (위에서 설명하였으므로 코드는 생략)

인접 리스트 방식

• 각 정점마다 연결된 다른 정점들을 리스트(또는 벡터 등) 형태로 저장
• 정점에 연결된 간선만 기록하므로, 희소 그래프(Sparse Graph)에서 메모리를 절약할 수 있음
• 특정 정점에 인접한 정점을 빠르게 조회할 수 있지만, 두 정점이 직접 연결되어 있는지 확인할 때는 해당 정점의 리스트를 순회해야 함

인접 행렬 방식

• 정점을 행과 열로 나타낸 2차원 배열(또는 벡터)을 사용해, 두 정점 간 연결 여부를 0 또는 1로 저장
• 모든 정점 쌍에 대한 정보를 담기 때문에, 조밀 그래프(Dense Graph)에서 유용함
• 두 정점이 연결되어 있는지를 인덱스로 바로 확인할 수 있지만, 정점 수가 $ n $ 개일 때 행렬의 크기가 $ n \times n $ 이 되므로 메모리 사용량이 커지게 됨

BFS 구현 방법

BFS는 시작 정점에서 가까운 정점부터 차례로 탐색하는 기법으로, 보통 큐(queue) 자료구조를 사용하여 구현한다.

• 큐(queue) 자료구조를 사용하여 구현
• 시작 정점을 방문했다고 표시하고, 해당 정점을 큐에 추가
• 큐가 빌 때까지 아래 과정을 반복
  • 큐에서 하나의 정점(u)을 꺼냄
  • u와 인접한 정점들 중 아직 방문하지 않은 정점을 찾아 방문 처리 후 큐에 추가

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n = 4;  // 정점(노드)의 개수
    // 인접 리스트(각 정점에 연결된 정점들을 저장)
    vector<vector<int>> adj(n);

    // 무방향 간선 정보 (0 - 1, 1 - 2, 2 - 3, 3 - 0)
    adj[0].push_back(1);
    adj[1].push_back(0);
    adj[1].push_back(2);
    adj[2].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(2);
    adj[3].push_back(0);
    adj[0].push_back(3);

    // 방문 여부 확인을 위한 벡터
    vector<bool> visited(n, false);

    // BFS를 위한 큐
    queue<int> q;

    // BFS 시작 (예: 0번 노드부터 탐색 시작)
    int start = 0;
    visited[start] = true;  // 시작 정점 방문 처리
    q.push(start);

    cout << "[BFS] 탐색 순서: ";

    while (!q.empty()) {
        // 큐에서 정점을 하나 꺼냄
        int u = q.front();
        q.pop();

        // 방문 순서 출력
        cout << u << " ";

        // u와 인접한 모든 정점을 확인
        for (int v : adj[u]) {
            // 방문하지 않은 정점이면 큐에 넣고 방문 처리
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    cout << endl;

    return 0;
}

BFS의 시간 복잡도

• 인접 리스트 사용 시
  • 각 정점을 한 번씩 방문하여 visited 체크
  • 각 간선도 최대 한 번씩(무방향인 경우 양방향으로 두 번) 확인
  • $ O(V + E) $
• 인접 행렬 사용 시
  • 한 정점을 꺼낼 때마다 $ V $ 개의 원소 확인
  • $ O(V^2) $

BFS 구현 시 주의사항

• 큐(queue) 사용
  • C++에서는 std::queue / Python에서는 collections.deque
• 방문 체크
  • BFS에서 중복 방문을 방지하지 않으면 무한 반복 가능
• 인접 리스트 정렬
  • 문제에서 "숫자가 작은 정점을 먼저 방문" 등의 요구가 있으면, 각 인접 리스트를 오름차순 정렬하고 BFS 진행
• 무방향 그래프 vs 유향 그래프
  • 무방향이면 양방향 인접 리스트로 저장하고, 유향이면 단방향에 대해서만 인접 리스트 저장
  • BFS 로직 자체는 다르지 않음 
• 거리 배열 활용
  • BFS로 최단 거리 문제를 풀 때, distance[u]를 저장해두면 유용
  • 첫 노드 시작 시 distance[start] = 0, 방문 시 distance[v] = distance[u] + 1

---

DFS와 BFS의 비교

특성	DFS	BFS
탐색 순서	한 경로로 끝까지(깊게) 간 뒤, 되돌아옴	거리(레벨) 기준으로 가까운 노드부터 차례로
자료구조	재귀 (recursive) 또는 스택 (stack)	큐 (queue)
주요 응용	백트래킹, 위상 정렬, 사이클 판별, 트리 순회	최단 경로(무가중치) 레벨 순회
시간 복잡도 (인접 리스트)	$ O(V + E) $	$ O(V + E) $

• DFS는 경로 단일 탐색(백트래킹)이나 재귀적 구조의 문제에서 편리
• BFS는 무가중치 그래프에서 최단 거리나 레벨별 구조를 탐색할 때 유리
• 시간 복잡도는 DFS와 BFS가 동일하지만, 탐색 순서와 특징이 서로 다름