C++로 익히는 DFS (깊이 우선 탐색)

개요

깊이 우선 탐색(Depth-First Search, DFS)은 그래프 또는 트리 구조에서 모든 노드를 방문하기 위한 대표적인 알고리즘이다. 이 알고리즘은 가능한 한 깊이 탐색을 진행한 후, 더 이상 탐색할 수 없을 때 백트래킹하여 다른 경로를 탐색한다. 본 글에서는 C++ 언어를 사용하여 DFS 알고리즘의 개념과 구현 방법을 설명한다.

설명

DFS는 스택(Stack) 자료구조 또는 재귀 호출을 사용하여 구현할 수 있다. 알고리즘의 기본 로직은 다음과 같다:

1. 시작 노드를 선택하고 방문 표시
2. 현재 노드와 인접한 미방문 노드가 있으면 해당 노드로 이동하고 방문 표시
3. 인접한 미방문 노드가 없으면 이전 노드로 백트래킹
4. 모든 노드를 방문할 때까지 2-3단계 반복

DFS는 경로 탐색, 위상 정렬, 사이클 감지, 연결 요소 찾기 등 다양한 문제 해결에 활용된다. 특히 미로 탈출, 퍼즐 게임 등의 문제에서 가능한 모든 경로를 탐색하는 데 효과적이다.

특징

DFS의 주요 특징은 다음과 같다:

1. 공간 효율성: 현재 경로 상의 노드만 메모리에 저장하므로 BFS(너비 우선 탐색)에 비해 메모리 사용량이 적다.
2. 완전 탐색: 그래프의 모든 노드를 방문하므로 완전한 탐색이 가능하다.
3. 시간 복잡도: 인접 리스트로 표현된 그래프의 경우 O(V+E), 인접 행렬의 경우 O(V²)이다. 여기서 V는 정점의 수, E는 간선의 수를 의미한다.
4. 비최적성: 최단 경로 문제에서는 최적해를 보장하지 않는다.
5. 백트래킹: 막다른 길에 도달하면 이전 분기점으로 돌아가 다른 경로를 탐색한다.

예제

아래는 C++로 구현한 DFS 알고리즘의 두 가지 방식(재귀와 스택)이다.

재귀를 이용한 DFS 구현

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

class Graph {
private:
    int V; // 정점의 수
    vector<vector<int>> adj; // 인접 리스트
    vector<bool> visited; // 방문 여부 저장

public:
    Graph(int v) : V(v) {
        adj.resize(v);
        visited.resize(v, false);
    }

    // 간선 추가 함수
    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }

    // DFS 탐색 함수
    void DFS(int start) {
        // 현재 노드를 방문한 것으로 표시
        visited[start] = true;
        cout << start << " ";

        // 모든 인접 정점에 대해 재귀적으로 DFS 호출
        for (int i : adj[start]) {
            if (!visited[i]) {
                DFS(i);
            }
        }
    }

    // 전체 그래프에 대한 DFS 탐색 시작
    void DFSTraversal(int start) {
        // 모든 정점을 미방문 상태로 초기화
        fill(visited.begin(), visited.end(), false);

        // 시작 정점부터 DFS 수행
        cout << "DFS 탐색 결과(재귀): ";
        DFS(start);
        cout << endl;
    }
};

스택을 이용한 DFS 구현

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

class Graph {
private:
    int V; // 정점의 수
    vector<vector<int>> adj; // 인접 리스트

public:
    Graph(int v) : V(v) {
        adj.resize(v);
    }

    // 간선 추가 함수
    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }

    // 스택을 이용한 DFS 구현
    void DFSIterative(int start) {
        vector<bool> visited(V, false);
        stack<int> s;

        // 시작 노드를 스택에 삽입
        s.push(start);

        cout << "DFS 탐색 결과(스택): ";

        while (!s.empty()) {
            // 스택에서 하나의 정점을 꺼냄
            int current = s.top();
            s.pop();

            // 해당 정점이 방문되지 않았다면 처리
            if (!visited[current]) {
                cout << current << " ";
                visited[current] = true;

                // 인접 정점들을 스택에 삽입 (역순으로 삽입하여 탐색 순서 조정)
                for (auto it = adj[current].rbegin(); it != adj[current].rend(); ++it) {
                    if (!visited[*it]) {
                        s.push(*it);
                    }
                }
            }
        }
        cout << endl;
    }
};

사용 예시

int main() {
    // 그래프 생성 (8개의 정점)
    Graph g(8);

    // 간선 추가
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    g.addEdge(2, 6);
    g.addEdge(6, 7);

    // DFS 탐색 실행
    g.DFSTraversal(0);
    g.DFSIterative(0);

    return 0;
}

미로 탐색 문제 예시

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

class Maze {
private:
    int rows, cols;
    vector<vector<int>> grid;
    vector<vector<bool>> visited;
    // 상, 우, 하, 좌 방향 이동
    int dr[4] = {-1, 0, 1, 0};
    int dc[4] = {0, 1, 0, -1};
    bool found;

public:
    Maze(int r, int c) : rows(r), cols(c), found(false) {
        grid.resize(r, vector<int>(c, 0));
        visited.resize(r, vector<bool>(c, false));
    }

    void setCell(int r, int c, int val) {
        grid[r][c] = val;
    }

    bool isValid(int r, int c) {
        return (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 1 && !visited[r][c]);
    }

    void solveMaze(int r, int c, int endR, int endC) {
        if (r == endR && c == endC) {
            found = true;
            cout << "미로의 출구를 찾았습니다!" << endl;
            return;
        }

        visited[r][c] = true;

        for (int i = 0; i < 4; i++) {
            int newR = r + dr[i];
            int newC = c + dc[i];

            if (isValid(newR, newC) && !found) {
                cout << "(" << r << "," << c << ") -> (" << newR << "," << newC << ")" << endl;
                solveMaze(newR, newC, endR, endC);
            }
        }

        // 백트래킹: 현재 경로가 출구로 이어지지 않는 경우
        if (!found) {
            visited[r][c] = false;
        }
    }
};

결론

DFS는 그래프와 트리를 탐색하는 기본적인 알고리즘으로, 백트래킹을 통해 모든 가능한 경로를 탐색할 수 있다. C++에서는 재귀 호출이나 스택을 사용하여 효율적으로 DFS를 구현할 수 있다. 그래프 탐색, 미로 찾기, 퍼즐 해결 등 다양한 문제에 활용 가능하며, 알고리즘의 원리를 이해하고 적절하게 응용하는 것이 중요하다. 특히 방문 여부를 체크하는 로직을 통해 무한 순환을 방지하고, 백트래킹을 통해 모든 가능한 경로를 효율적으로 탐색할 수 있다.

참고문헌

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press. - https://mitpress.mit.edu/books/introduction-algorithms-third-edition
2. Sedgewick, R., & Wayne, K. (2011). Algorithms. Addison-Wesley Professional. - https://algs4.cs.princeton.edu/
3. GeeksforGeeks - Depth First Search - https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
4. C++ Reference - Standard Template Library - https://en.cppreference.com/w/cpp/container