그래프 깊이 우선 탐색(DFS) 완벽 정리: 개념, 알고리즘, C++ 구현까지

깊이 우선 탐색(Depth-First Search, DFS)은 그래프를 순회(traversal)하는 대표적인 알고리즘입니다. 하나의 시작 정점이 주어지면, 인접한 정점을 발견하는 즉시 해당 정점으로 먼저 이동하고, 같은 방식으로 계속해서 탐색을 이어갑니다.

DFS는 이름 그대로 가능한 한 깊게 경로를 따라 들어간 뒤, 더 이상 나아갈 곳이 없으면 백트래킹(backtracking)을 통해 이전 정점들로 되돌아와 아직 탐색하지 않은 새로운 경로를 찾습니다.

DFS를 반복문(iterative) 방식으로 구현하려면 스택(stack) 자료구조가 필요합니다. 반면 재귀(recursive) 방식으로 구현하면 함수 호출 시 내부적으로 사용되는 콜 스택(call stack)이 그 역할을 대신하기 때문에 별도의 외부 스택이 필요하지 않습니다.

입력과 출력

DFS의 입력은 그래프의 인접 행렬(Adjacency Matrix)이며, 출력은 시작 정점에서부터의 DFS 순회 순서입니다.

입력:
그래프의 인접 행렬

      A B C D E F
  A   0 1 1 1 0 0
  B   1 0 0 1 1 0
  C   1 0 0 1 1 0
  D   1 1 1 0 1 1
  E   0 1 0 1 0 1
  F   0 0 1 1 1 0

출력:
DFS 순회 결과: C F E B D A

알고리즘 동작 원리

dfs(vertices, start)

입력: 그래프의 모든 정점 목록과 시작 노드
출력: 그래프의 모든 노드를 순회합니다.

Begin
    모든 노드의 상태를 '방문하지 않음'으로 초기화
    시작 노드를 스택에 push

    while 스택이 비어 있지 않은 동안:
        스택에서 요소를 pop 하여 u에 저장
        노드 u 출력

        if u가 아직 방문되지 않았다면:
            u를 방문 처리
            for u와 연결된 모든 노드 i:
                if i번째 정점이 방문되지 않았다면:
                    i번째 정점을 스택에 push
                    i번째 정점을 방문 처리
    done
End

핵심 포인트

스택 활용: 가장 최근에 발견한 정점을 우선 탐색하기 위해 LIFO(Last-In, First-Out) 구조의 스택을 사용합니다.
방문 여부 관리: 각 정점의 상태(state)를 추적하여 같은 정점을 중복 방문하지 않도록 합니다.
백트래킹: 더 이상 확장할 수 없는 경로에 도달하면 자동으로 이전 분기점으로 돌아갑니다.

C++ 구현 예제

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다. STL의 stack 컨테이너를 사용해 반복문 방식으로 작성했습니다.

#include<iostream>
#include<stack>
using namespace std;
#define NODE 6

typedef struct node {
    int val;
    int state; // 방문 상태
}node;

int graph[NODE][NODE] = {
    {0, 1, 1, 1, 0, 0},
    {1, 0, 0, 1, 1, 0},
    {1, 0, 0, 1, 0, 1},
    {1, 1, 1, 0, 1, 1},
    {0, 1, 0, 1, 0, 1},
    {0, 0, 1, 1, 1, 0}
};

void dfs(node *vertex, node start) {
    node u;
    stack<node> myStack;

    for(int i = 0; i<NODE; i++) {
        vertex[i].state = 0;  // 미방문 상태로 초기화
    }

    myStack.push(start);
    while(!myStack.empty()) {
        // pop 후 노드 출력
        u = myStack.top();
        myStack.pop();
        cout << char(u.val+'A') << " ";

        if(u.state != 1) {
            // 방문 상태로 갱신
            u.state = 1;
            vertex[u.val].state = 1;

            for(int i = 0; i<NODE; i++) {
                if(graph[i][u.val]) {
                    if(vertex[i].state == 0) {
                        myStack.push(vertex[i]);
                        vertex[i].state = 1;
                    }
                }
            }
        }
    }
}

int main() {
    node vertices[NODE];
    node start;
    char s;

    for(int i = 0; i<NODE; i++) {
        vertices[i].val = i;
    }

    s = 'C';  // 시작 정점: C
    start.val = s-'A';
    cout << "DFS Traversal: ";
    dfs(vertices, start);
    cout << endl;
}

실행 결과

DFS Traversal: C F E B D A

결과 해석

시작 정점 C에서 출발하면, C에 인접한 F를 먼저 스택에 넣고 탐색을 진행합니다. 이후 F → E → B → D 순서로 깊이 우선으로 이동하며, 마지막에 남은 정점 A를 방문하면서 순회가 종료됩니다. 이처럼 DFS는 너비보다 깊이를 우선으로 탐색하기 때문에, 같은 그래프라도 BFS(너비 우선 탐색)와는 다른 방문 순서를 보입니다.

마무리

DFS는 시간 복잡도가 O(V+E)(V는 정점 수, E는 간선 수)로 효율적이며, 미로 찾기, 사이클 검출, 연결 성분(component) 탐색, 위상 정렬 등 다양한 그래프 문제의 기반으로 활용됩니다. 스택의 동작 원리만 이해하면 재귀 버전과 반복 버전 모두 어렵지 않게 구현할 수 있으니, 직접 코드를 변형해 다양한 그래프에 적용해 보시길 권장합니다.