[c++] 깊이 우선 탐색(Depth First Search, DFS) 알고리즘

08 Dec 2023

깊이 우선 탐색(Depth First Search, DFS)은 그래프를 탐색하기 위한 알고리즘 중 하나로, 더 이상 방문할 노드가 없을 때까지 최대한 깊게 들어가서 모든 노드를 탐색합니다. 이는 스택(Stack) 자료구조를 사용하여 구현할 수 있습니다.

알고리즘 동작 방식

DFS 알고리즘은 다음과 같이 동작합니다.

시작 노드를 스택에 넣고 방문 표시를 합니다.
스택에서 노드를 꺼내어 인접한 노드들을 방문하지 않은 순서로 스택에 넣고 방문 표시를 합니다.
스택이 빌 때까지 2단계를 반복합니다.

장단점

장점

간단한 구현으로써 많은 문제에 적용할 수 있습니다.
같은 깊이에 있는 노드를 탐색할 때 효과적입니다.

단점

최단 경로를 구할 수 없습니다.
무한히 깊은 경로에 빠질 수 있습니다.

예시 코드

#include <iostream>
#include <vector>
#include <stack>

std::vector<std::vector<int>> graph; // 그래프 구현은 문제에 따라 다를 수 있음
std::vector<bool> visited;

void dfs(int start) {
    std::stack<int> s;
    s.push(start);
    
    while (!s.empty()) {
        int current = s.top();
        s.pop();
        
        if (visited[current]) {
            continue;
        }
        
        visited[current] = true;
        
        for (int next : graph[current]) {
            if (!visited[next]) {
                s.push(next);
            }
        }
    }
}

참고 자료

DFS 위키백과
깊이 우선 탐색 (DFS) 알고리즘 - 나무위키
Introduction to the Design and Analysis of Algorithms, Anany Levitin, Maria Levitin, Addison-Wesley