03. DFS(Depth-First Search)

1. 특징 및 복잡도

• 정의: 다음 분기(Branch)로 넘어가기 전, 현재 분기를 끝까지 탐색하는 방식.
• 시간 복잡도: O(V+E) (인접 리스트 기준)
• 공간 복잡도: O(H) (H는 그래프의 최대 깊이)

2. 장점과 단점

✅ 장점

• BFS 대비 저장 공간 수요가 적음 (현재 경로의 노드만 저장).
• 목표 노드가 깊은 곳에 있을 때 효율적임.

❌ 단점

• 최단 경로를 보장하지 않음.
• 해가 없는 경로에 깊게 빠져 시간을 낭비할 수 있음.

3. 구현 방식 (C++)

재귀는 직관적이고 스택은 안정적이다.

// 재귀 버전
void DFS(int cur) {
    visited[cur] = true;
    for(int nxt : adj[cur]) {
        if(visited[nxt]) continue;
        DFS(nxt);
    }
}

// 스택 버전
stack<int> s;
s.push(start);
while(!s.empty()) {
    int cur = s.top(); s.pop();
    if(visited[cur]) continue; 
    visited[cur] = true;
    for(int nxt : adj[cur]) {
        if(visited[nxt]) continue;
        s.push(nxt);
    }
}

4. 구현 시 주의사항

• 스택 오버플로우 방지: 재귀 방식은 구현이 간단하지만, 깊이가 너무 깊어지면 시스템 스택 제한으로 인해 런타임 에러가 발생할 수 있다.
• 메모리 사용량: 재귀는 경로상의 노드만 저장하여 메모리 효율이 좋지만, 스택 버전은 주변 인접 노드를 모두 스택에 넣으므로 상대적으로 메모리를 더 많이 소모한다.
• 안정성: 대량의 노드를 탐색하거나 깊이가 예측 불가능한 경우 명시적인 스택 객체를 사용하는 것이 안전하다.

5. 실전 사례 및 번외

• 사례: 백트래킹, 게임 내 시나리오 분기 시스템(엔딩 트리 탐색 등).
• 번외: 스택 버전은 큐(BFS)와 달리 데이터를 '꺼낼 때' 방문 처리를 해야 재귀와 동일한 순서로 탐색이 진행된다.