DFS 공부

1. DFS를 구현하는 대표적인 두가지 방법

 

[1] 재귀 호출(Recursive)

DFS를 함수의 재귀 호출(Recursion) 로 구현하는 방법.
현재 노드를 방문하고, 연결된 노드를 재귀적으로 방문하는 방식.

void DFS(int node) {
    visited[node] = true;
    foreach (int next in graph[node]) {
        if (!visited[next]) {
            DFS(next);
        }
    }
}

 

장점

• 코드가 간결하고 이해하기 쉽다.
• 함수 호출 스택을 그대로 활용하므로 별도의 자료구조(Stack)를 사용할 필요가 없다.
• 문제의 구조가 재귀적인 경우(트리 탐색 등) 자연스럽게 매칭된다.

 

단점

• 호출 깊이 제한(Stack Overflow): 그래프가 깊거나 노드 수가 많으면 스택 초과 에러 발생 가능.
• 디버깅이 어렵고, 재귀 호출이 많은 경우 성능이 불안정할 수 있다.

 

 

[2] 명시적인 스택(Stack)

Stack 자료구조를 직접 사용하여 DFS를 구현하는 방법.
재귀를 사용하지 않고, 스택에 직접 노드를 push/pop하면서 탐색.

void DFS(int start) {
    Stack<int> stack = new Stack<int>();
    stack.Push(start);
    visited[start] = true;

    while (stack.Count > 0) {
        int node = stack.Pop();
        foreach (int next in graph[node]) {
            if (!visited[next]) {
                stack.Push(next);
                visited[next] = true;
            }
        }
    }
}

 

장점

• 스택 오버플로우 걱정 없이 깊은 탐색이 가능하다.
• 스택의 동작 과정을 직접 제어할 수 있어 메모리 관리에 유리하다.
• 재귀 호출을 사용하지 않으므로 디버깅이 상대적으로 쉽다.

 

단점

• 코드가 재귀 방식보다 길고 복잡하다.
• 스택을 명시적으로 관리해야 하므로 구현 부담이 있다.

 

요약 표

방식	장점	단점
재귀 호출	코드가 간결, 함수 호출 스택 활용	깊은 그래프에서 스택 오버플로우 위험
명시적 스택	스택 오버플로우 없음, 디버깅 쉬움	코드 복잡도 증가, 스택 직접 관리 필요

 

• 노드 수가 적거나 트리 형태 → 재귀 호출 간결
• 노드 수가 많고 깊이도 깊으면 → 명시적 스택 선호