[Algorithm] DFS (Depth-First Search) : 깊이 우선 탐색

김형준·2025년 8월 6일

Algorithm

목록 보기

2/2

01. 깊이 우선 탐색 (DFS, Depth-First Search) 개요

01-1. DFS란?

Depth First Search의 약자로, 그래프 순회 방식의 일종입니다. 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색합니다.

(출처: 나무위키 https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89)

01-2. DFS를 쓰는 상황

DFS와 비슷하게 BFS가 있습니다. 단순 검색 속도는 BFS보다 느리지만, 순회(traversal), 모든 노드를 방문)를 할 경우 많이 쓰입니다.

01-3. DFS의 특징

재귀 함수를 활용합니다.
방문한 노드를 체크해야합니다.
(ex. 방문 전: visited = false, 방문 후: visited = true)

01-4. DFS 과정

02. DFS 구현

02-1. C++ 구현

const int MAX = 100'001;

bool visited[MAX]; // 방문 배열. visited[node] = true이면 node는 방문이 끝난 상태이다.

void dfs(const vector<int> graph[], int current) { // graph는 인접 리스트, current는 현재 노드
    visited[current] = true; // current 방문

    for(int next: graph[current]) { // current의 인접 노드를 확인한다. 이 노드를 next라고 하자.
        if(!visited[next]) { // 만일 next에 방문하지 않았다면
            dfs(graph, next); // next 방문
        }
    }
}

위 코드가 인터넷에 돌아다니는 DFS 코드입니다.
아래는 함수 작동 순서를 확인하는 로그를 찍는 코드입니다.

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

int N = 5;  // 정점 수
vector<vector<int>> adj = {
    {1, 2, 4},      // 0번
    {0, 2},         // 1번 정점에 인접한 노드들
    {0, 1, 3},      // 2번
    {2, 4},         // 3번
    {0, 2, 3},      // 4번
};
vector<bool> visited(N, false);
vector<int> result;

// 깊이(depth)에 맞춘 들여쓰기 문자열 반환
string indent(int depth) {
    return string(depth * 2, ' ');
}

// 재귀 DFS
void dfs(int u, int depth) {
    cout << indent(depth) << "[ENTER] node " << u << "\n";
    visited[u] = true;
    result.push_back(u);
    cout << indent(depth) << "change \'visited[" << u << "]\' to true" << "\n";
    for (int v : adj[u]) {
        cout << indent(depth) << "  \'visited[" << v << "]\' is " << visited[v] << "\n";
        if (!visited[v]) {
            cout << indent(depth) << "  -> go to " << v << "\n";
            dfs(v, depth + 1);
            cout << indent(depth) << "  <- return to " << u << "\n";
        }
        else {
            cout << indent(depth) << "  (skip visited " << v << ")\n";
        }
    }
    cout << indent(depth) << "[EXIT] node " << u << "\n";
}

int main() {
    int start = 0;  // 시작 정점

    cout << "=== DFS Start from " << start << " ===\n";
    dfs(start, 0);
    cout << "=== DFS End ===\n\n";

    cout << "[Result] : ";
    for (int i = 0; i < N; i++) {
        cout << result.at(i) << " ";
    }

    return 0;
}