[알고리즘] DFS(Depth-First Search, 깊이 우선 탐색) 문제 풀이 가이드

개념

DFS(Depth-First Search,깊이 우선 탐색) 는 그래프나 트리와 같은 자료구조에서 탐색을 진행할 떄 사용하는 대표적인 알고리즘입니다.
특정 노드를 시작점으로 잡고 최대한 깊은 경로까지 탐색하다가, 더 이상 탐색할 곳이 없으면 백트래킹을 통해 돌아오며 탐색하지 않은 경로를 다시 탐색합니다.

즉, 깊게 먼저 들어가며 탐색하는 방식입니다.

---

DFS의 핵심 원리

하나의 노드를 선택해 방문한 후, 인접한 노드를 따라 갈 수 있는 곳까지 깊이 들어갑니다.
더 이상 이동할 곳이 없으면 이전 노드로 돌아와서 다시 탐색을 시작합니다.
방문한 곳을 기록해, 이미 방문한 노드는 재탐색하지 않습니다.

즉, “한쪽 방향 끝까지 먼저 파고든다”라는 생각하면 직관적으로 이해할 수 있습니다.

---

DFS 탐색 순서 예시

      1 (root node)
    /   \
   2     5
  / \   / \
 3   4 6   7

탐색 순서: 1 → 2 → 3 → 4 → 5 → 6 → 7

---

DFS의 시간 복잡도

일반적으로 O(N) ~ O(N²) 까지 다양합니다. 다만, 각 문제의 요구조건에 따라 가지치기(pruning) 기법으로 활용하여 탐색 횟수를 크게 줄일 수 있습니다.
즉, 조건에 부합하지 않은 탐색 경로를 미리 차단(return)하여 불필요한 탐색을 방지할 수 있습니다.

---

Java 코드로 DFS 알고리즘 가이드 보기

// 그래프를 인접리스트로 표현 (예시)
List<Integer>[] graph = new ArrayList[5];
for (int i = 0; i < graph.length; i++) {
    graph[i] = new ArrayList<>();
}
// 간선 연결 예시 (0→1, 0→2, 1→3, 2→4)
graph[0].add(1);
graph[0].add(2);
graph[1].add(3);
graph[2].add(4);

boolean[] visited = new boolean[5];  // 방문 여부 체크

dfs(0, graph, visited, 0);  // 0번 노드에서 DFS 탐색 시작, 초기 깊이는 0

// DFS 재귀 메서드 구현
public void dfs(int node, List<Integer>[] graph, boolean[] visited, int depth) {
    // 특정 조건에 따라 탐색을 중단할 수 있음 (가지치기)
    // 예시: 깊이가 3 이상이면 탐색 중지
    // if (depth >= 3) return;

    visited[node] = true; // 현재 노드를 방문 처리, 다음 깊이를 위해
    System.out.println("방문 노드: " + node + ", 현재 깊이: " + depth);

    // 현재 노드와 연결된 모든 인접 노드를 탐색
    for (int next : graph[node]) {
        if (!visited[next]) { // 방문하지 않은 노드만 탐색
            dfs(next, graph, visited, depth + 1);
        }
    }

    // 다른 경로 탐색을 위한 백트래킹 처리
    visited[node] = false;
}

---

코드 흐름 간략 정리

• 현내 노드 방문 처리(visited[node] = true)
• 현재 노드의 모든 인접 노드 탐색
• 방문하지 않은 인접 노드가 있다면 재귀적으로 방문
• 모든 인점 노드를 탐색하면 이전 호출로 되돌아가 계속 탐색(백트래킹)
• 조건에 따라 가지치기하여 탐색 성능 향상 가능

---

DFS가 유용한 문제

• 그래프 탐색 및 경로 탐색 관련 문제
  • 길찾기: 특정 노드에서 도달 가능한 모든 노드 찾기
• 모든 경우의 수를 고려해야하는 완전탐색 및 백트래킹 문제
  • 미로 찾기, 조합(Combination), 순열(Permutation) 등
• 트리 순회 문제
  • 전위(Pre-order)
  • 정위(Post-order)
  • 후위(In-order)
• 연결 요소(Connected Component) 개수 찾기 문제

---

요약

DFS는 그래프나 트리처럼 특정 노드부터 최대한 깊이 들어가면서 탐색하는 알고리즘이며 가능한 깊게 탐색을 진행하고, 더 이상 탐색할 수 없을 때 이전으로 되돌아가 탐색하지 않은 노드를 다시 방문하는 방식입니다.

DFS는 탐색 대상의 전체 구조를 파악하거나 완전 탐색할 때 유용합니다.

반면, 최단거리와 같이 최적의 경로를 찾는 문제에서는 일반적으로 BFS가 더 효율적이며, 그래프가 매우 깊고 넖을 때 DFS는 스택 오버플로우가 발생할 가능성이 있습니다.