DFS (Depth-First Search) [깊이 우선 탐색]

1. 핵심 개념

• 한 방향으로 깊이 들어감

• 갈 수 있는 곳까지 가본 뒤, 되돌아가서 다른 경로 탐색

• 재귀 또는 스택으로 구현 가능

2. DFS 기본 구조 (재귀 방식)

void dfs(Node node, boolean[] visited) {
    visited[node] = true;     // 현재 노드 방문 처리

    for (Node next : node.neighbors) {
        if (!visited[next]) {
            dfs(next, visited); // 다음 노드로 재귀 호출
        }
    }
}

3. DFS의 특징

4. DFS 활용 예시

• 백트래킹 문제 (예: 순열, 조합, 최대 탐색)

• 미로 탐색

• 트리 구조 순회

• 모든 경우의 수 탐색

• 피로도 문제에서 최대 던전 탐험 수 찾기

5. DFS vs BFS 차이

6. DFS 구현 방법 정리

• 재귀 사용: 가장 직관적이고 간단

• 스택 사용: 명시적 스택으로 구현 가능

• 방문 배열: 중복 탐색 방지를 위해 사용