[C++] 깊이 우선 탐색 (DFS)

프로그래밍에서 탐색 (Searching)과 순회 (Traversal)는 매우 중요한 개념이다. 그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 깊이 우선 탐색 (Depth-First Search, DFS)은 가장 널리 사용되는 탐색 방법 중 하나다.

---

DFS가 무엇이고, 어느 때 사용하는지 정리하며, 스택과 재귀함수 (recursive)로 구현된 코드를 통해 이해를 도울 수 있도록 한다.

깊이 우선 탐색이란?

깊이 우선 탐색 (DFS)는 그래프 완전 탐색 방법 중 하나이다. 시작 노드에서 한 쪽 분기를 정하여 가볼 수 있는 최대 깊이까지 탐색을 마치고 다른 쪽 분기에서 다시 탐색을 수행하는 알고리즘이다. 모든 노드를 찾는 것이 핵심이지 경로를 고려하는 알고리즘은 아니기 때문에 최적화를 위해서는 몇 가지 조건들이 추가되어야 할 것이다. (알고리즘 문제를 풀 때 DFS를 "응용"해야 하는 것이지 바로 갖다쓸 수 없다는 것.)

위 그림과 같은 구조에서 모든 지점을 탐색하면서 중복되게 방문하는 노드가 없도록 하고 싶다면, 어떤 방법이 있을까?

1번에서 시작하면 3-4-6-2-5번의 순서로 이동하거나, 2-6-4-3번을 방문 후 5번을 방문할 수 있다.

 

이를 알고리즘으로 만들기 위해서 필요한 것은 인접 노드 리스트, 방문 여부 체크이다. 그리고 이를 함수로 만들 때 데이터의 흐름 방식이 후입선출 (LIFO)의 방식으로, 재귀함수나 스택을 사용할 수 있다.

 

그림으로 표현하기 쉬운 스택으로 정리해보면, 초기 세팅을 아래와 같이 할 수 있다.

DFS 초기 세팅. 왼쪽부터 그래프, 인접 노드 리스트, 방문여부 체크리스트, 스택

시작하면서 1을 방문한 것과 같으므로 방문 여부 체크에 True로 설정되어 있는 것을 확인할 수 있다.

다음으로는 스택에 있는 1을 빼고 1의 인접 노드 2와 3을 스택에 쌓는 작업이다.

이 상태에서 다음으로 방문할 노드를 정한다. 스택에서 가장 위에 있는 3을 다음 목적지로 정했다.

스택에서 가장 위에 있는 3을 빼면서 그래프에서는 노드 3을 방문한다. 체크리스트에서는 3이 T로 바뀐다.

3이 스택에서 빠지면서 3의 인접 노드 리스트에 있는 1, 4중 방문 이력이 없는 4를 스택에 올려놓을 수 있다.

같은 방식으로 4가 스택의 가장 위에 있으므로 노드 4를 방문하면서 스택에서 빼고 인접 노드 리스트에 있는 3, 6 중 방문 이력이 없는 6만 스택에 넣는다. 또 반복하면 6의 인접 노드 리스트 2, 4 중 2를 아직 방문하지 않았으므로 2를 넣을 수 있을 것이다. 그런데 여기서 2는 이미 스택에 들어있으므로 이를 그대로 코드로 구현하면 잘못된 출력이 나올 것이다.

그래서 코드로 구현할 때에는 스택에 들어가는 값들은 바로 방문 여부 리스트에서 True로 바꿔주어야 할 것이다.

DFS 구현 방법

지금까지 정리한 내용을 코드로 구현하면 아래와 같다. 임의의 노드를 시작점으로 잡았을 때의 결과를 보여주기 위해 for문을 이용했다.

- 스택을 이용한 DFS 구현

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

vector<vector<int>> graph;
vector<bool> visited;

void dfs_stack(int start) {
    // 초기 세팅
    stack<int> s;
    s.push(start);
    visited[start] = true;

    while (!s.empty()) {
        int node = s.top();
        s.pop();
        cout << node << " ";
		
        // 스택에 쌓는 순서에 따라 for문을 다르게 쓸 수 있음
        for (int i = graph[node].size() - 1; i > -1; i--) {
            int next = graph[node][i];
            if (!visited[next]) {
                visited[next] = true;
                s.push(next);
            }
        }
    }
}

int main() {
    int n = 6;
    graph.resize(n);
    visited.resize(n, false);

    // 예시 그림의 인접 노드
    graph[0] = {1, 2};
    graph[1] = {0, 4, 5};
    graph[2] = {0, 3};
    graph[3] = {2, 5};
    graph[4] = {1};
    graph[5] = {1, 3};

    // 시작 노드가 1일 때부터 6일 때까지 모든 경우에 대해 완전 탐색 가능 여부 확인
    for (int i = 0; i<n; i++) {
        dfs_stack(i);
        cout << endl;
        visited.clear();
        visited.resize(n, false);
    }
    return 0;
}

코드를 실행시켜보면 중복되는 노드 없이 완전 탐색을 수행하는 것을 확인할 수 있다.

- 재귀함수를 이용한 DFS 구현

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

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int node) {
    visited[node] = true;
    cout << node << " ";

    // 인접 노드를 방문하기 전에 정렬 (스택 방식과 동일한 순서 유지)
    sort(graph[node].begin(), graph[node].end());
    
    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

int main() {
    int n = 6;
    graph.resize(n);
    visited.resize(n, false);
    
    // 그래프 예시
    graph[0] = {1, 2};
    graph[1] = {0, 4, 5};
    graph[2] = {0, 3};
    graph[3] = {2, 5};
    graph[4] = {1};
    graph[5] = {1, 3};
    
    for (int i = 0; i<n; i++) {
        dfs(i);
        cout << endl;
        visited.clear();
        visited.resize(n, false);
    }
    return 0;
}

스택 방식과 동일한 결과를 출력하는 것을 볼 수 있으며, 스택에서도 마찬가지이지만 인접 노드를 어떤 순서로 보는지에 따라 결과가 달라지는 것을 볼 수 있다. 

DFS의 장단점

위의 내용을 읽었다면 어느정도 짐작할 수 있겠지만, 이것만으로 사람이 보고 푸는 것처럼 깔끔한 답을 내기는 어려울 수 있다. 그렇지만 간단하게 완전탐색을 구현할 수 있다는 점에서 메리트가 있는 알고리즘이라는 것을 느낄 수 있었다.

 

DFS의 장단점을 정리해보면 아래와 같다.

장점

• 메모리 사용량이 적음: BFS에 비해 큐 대신 스택(또는 재귀 호출)로 동작하여 메모리 소비가 적다.
• 경로 탐색에 유리함: 특정 노드까지 도달하는 경로를 찾는 문제에서 효과적이다.
• 백트래킹과 조합 문제에서 강력함: 재귀 구조와 잘 맞아떨어져 최적화 문제(예: 순열, 조합)에서 자주 사용된다.
• 구현이 간단함: 재귀를 활용하면 직관적인 코드 작성이 가능하다.목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

• 최단 경로 보장이 안됨: 먼저 발견한 길을 따라가므로 최단 거리를 찾는 문제에는 부적절하다.
• 무한 루프 발생 가능성: 사이클이 있는 그래프에서 방문 처리를 하지 않으면 무한 루프에 빠질 위험이 있다.
• 재귀 방식에서는 스택 오버플로우 위험: 그래프의 깊이가 너무 깊으면 재귀 호출이 많이 발생해 프로그램이 강제 종료될 수 있다.
• 모든 경로를 탐색하는 경우 비효율적: 최적의 해를 찾아야 하는 경우 불필요한 탐색이 많아질 수 있다.해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다.

---

대표적인 완전 탐색 방법인 DFS에 대해서 정리해보았다. 위에서도 언급했지만, 어렵지 않게 함수로 만들 수 있다는 장점이 있다. 그러나 몇 가지 단점이 있어 이 방법을 실제 문제에 적용하기 위해서는 변수를 추가하거나 알고리즘을 수정하는 등의 방법을 통해 문제 해결이 되어야 할 것이다. 이는 예제들을 풀어보면서 더 감을 잡아야할 것 같다.

- 같이 보면 좋은 글: BFS

[C++] 넓이 우선 탐색 (BFS)

- 같이 보면 좋은 글: DFS 예제

[C++] DFS 관련 문제 (백준 2023번, 신기한 소수)

[C++] DFS 관련 문제 (백준 13023번, ABCDE)