C++로 DFS(깊이 우선 탐색) 순회 과정을 단계별로 출력하는 프로그램

이 튜토리얼에서는 주어진 그래프에서 깊이 우선 탐색(Depth First Search, DFS)을 수행하면서 순회의 모든 단계를 출력하는 C++ 프로그램을 다룹니다.

여기서 출력되는 단계에는 자식 노드를 방문한 뒤 부모 노드로 되돌아가는 백트래킹(backtracking) 과정까지 포함됩니다.

동작 원리

DFS를 수행하는 동안 각 노드를 순회하면서 동시에 부모 노드와 사용된 간선(edge) 정보를 저장합니다. 순회 중 어떤 노드의 인접 간선이 이미 방문된 상태라면, 해당 노드로 되돌아가는 지점을 DFS 순회의 한 단계로서 화면에 출력할 수 있습니다.

즉, 앞으로 나아가며 새로운 노드를 방문할 때와 더 이상 방문할 곳이 없어 이전 노드로 되돌아올 때의 모든 경로가 순서대로 기록되므로, DFS의 전체 진행 과정을 그대로 추적할 수 있습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
vector<int> adj[N];

// DFS 순회의 각 단계를 출력하는 함수
void dfs_steps(int u, int node, bool visited[],
    vector<pair<int, int>> path_used, int parent, int it){
    int c = 0;
    for (int i = 0; i < node; i++)
        if (visited[i])
            c++;
    // 모든 노드를 방문했다면 종료
    if (c == node)
        return;

    // 현재 노드를 방문 처리
    visited[u] = true;
    path_used.push_back({ parent, u });
    cout << u << " ";

    // 아직 방문하지 않은 인접 노드로 이동
    for (int x : adj[u]){
        if (!visited[x])
            dfs_steps(x, node, visited, path_used, u, it + 1);
    }

    // 저장된 경로를 따라 부모 노드로 백트래킹
    for (auto y : path_used)
        if (y.second == u)
            dfs_steps(y.first, node, visited,
            path_used, u, it + 1);
}

void dfs(int node){
    bool visited[node];
    vector<pair<int, int>> path_used;
    for (int i = 0; i < node; i++)
        visited[i] = false;
    dfs_steps(0, node, visited, path_used, -1, 0);
}

void add_edge(int u, int v){
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int main(){
    int node = 11, edge = 13;
    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 5);
    add_edge(1, 6);
    add_edge(2, 4);
    add_edge(2, 9);
    add_edge(6, 7);
    add_edge(6, 8);
    add_edge(7, 8);
    add_edge(2, 3);
    add_edge(3, 9);
    add_edge(3, 10);
    add_edge(9, 10);
    dfs(node);
    return 0;
}

출력 결과

0 1 5 1 6 7 8 7 6 1 0 2 4 2 9 3 10

코드 설명

위 코드에서 dfs_steps() 함수는 재귀적으로 호출되며 다음과 같이 동작합니다.

1. 종료 조건 확인: 방문한 노드의 개수를 세어 전체 노드 수와 같으면 탐색을 종료합니다.
2. 방문 처리 및 출력: 현재 노드를 방문 처리하고, 부모 노드와의 연결 정보를 path_used 벡터에 저장한 뒤 노드 번호를 출력합니다.
3. 자식 노드 탐색: 인접 리스트를 확인하여 아직 방문하지 않은 노드가 있으면 재귀 호출로 깊이 들어갑니다.
4. 백트래킹: 더 이상 방문할 인접 노드가 없으면 저장해 둔 경로 정보를 이용해 부모 노드로 되돌아가며, 이때도 노드 번호가 출력되어 되돌아가는 과정이 기록됩니다.

실행 결과를 보면 0 → 1 → 5까지 내려간 뒤 다시 1로 돌아오고, 이후 6 → 7 → 8을 거쳐 7 → 6 → 1 → 0으로 백트래킹하는 전체 과정이 순서대로 출력되는 것을 확인할 수 있습니다.