[알고리즘] DFS(깊이 우선 탐색) 개념 및 구현

[알고리즘] DFS(깊이 우선 탐색) 개념 및 구현

1. DFS(깊이 우선 탐색)란?

DFS(Depth-First Search, 깊이 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 한 노드에서 출발해 **최대한 깊이 탐색한 후, 다시 돌아와서 다른 경로를 탐색하는 방식**입니다.

일반적으로 **스택(Stack) 또는 재귀(Recursion)**을 이용하여 구현할 수 있습니다.

✔️ DFS의 시간 복잡도: O(V + E) (V: 노드 수, E: 간선 수)

---

2. DFS의 동작 원리

1. 시작 노드를 방문하고, 방문한 노드를 **스택에 저장**
2. 해당 노드에서 **방문하지 않은 인접 노드**를 찾고, 있다면 방문
3. 더 이상 방문할 노드가 없으면 **스택에서 꺼내면서 뒤로 이동**
4. 이 과정을 반복하여 모든 노드를 탐색

---

3. DFS 코드 구현 (반복문 & 재귀 방식)

✅ 1) DFS - 재귀(Recursion) 방식

import java.util.*;

public class DFSSample {
    static boolean[] visited;
    static List> graph = new ArrayList<>();

    public static void dfs(int node) {
        visited[node] = true;
        System.out.print(node + " "); // 방문한 노드 출력

        for (int next : graph.get(node)) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }

    public static void main(String[] args) {
        int n = 6; // 노드 개수
        visited = new boolean[n + 1];

        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 추가
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(2).add(4);
        graph.get(2).add(5);
        graph.get(3).add(6);

        System.out.println("DFS 탐색 결과:");
        dfs(1);
    }
}

✅ 2) DFS - 스택(Stack) 활용 방식

import java.util.*;

public class DFSSampleStack {
    static boolean[] visited;
    static List> graph = new ArrayList<>();

    public static void dfsStack(int start) {
        Stack stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop();

            if (!visited[node]) {
                visited[node] = true;
                System.out.print(node + " ");

                // 인접 노드를 역순으로 추가 (작은 번호부터 방문하려면 정렬 필요)
                Collections.reverse(graph.get(node));
                for (int next : graph.get(node)) {
                    if (!visited[next]) {
                        stack.push(next);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int n = 6; // 노드 개수
        visited = new boolean[n + 1];

        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 추가
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(2).add(4);
        graph.get(2).add(5);
        graph.get(3).add(6);

        System.out.println("DFS 탐색 결과:");
        dfsStack(1);
    }
}

---

4. DFS가 사용되는 대표적인 예시

• ✔ **미로 탐색** (경로 찾기)
• ✔ **그래프의 연결 요소 개수 찾기**
• ✔ **백트래킹(Backtracking)** (경우의 수 찾기)
• ✔ **강한 연결 요소(SCC) 탐색**

---

5. BFS와 비교

알고리즘	구현 방식	주요 특징	적용 사례
DFS	스택 / 재귀	최대한 깊이 탐색 후 백트래킹	백트래킹, 미로 탐색
BFS	큐(Queue)	최단 경로 탐색에 유리	최단 거리 문제, 네트워크 탐색

---

🔍 결론

DFS는 **그래프 탐색에서 가장 기본적이면서도 강력한 알고리즘**으로, 다양한 문제 해결에 활용됩니다. 특히 백트래킹 문제 해결에 많이 사용됩니다.

이제 DFS를 이해했다면, **BFS(너비 우선 탐색)와 비교해보는 것도 추천합니다!**

---

📖 관련 알고리즘도 함께 확인하세요!

👉 다른 알고리즘 문제 풀이 보러 가기