DFS

---

🧭 DFS

정의

DFS(Depth-First Search)는 그래프나 트리를 깊이 우선으로 탐색하는 알고리즘이다.

DFS는 한 방향으로 최대한 깊게 들어간 뒤 더 이상 갈 수 없으면 되돌아오는 방식으로 동작한다.
재귀나 스택으로 구현하는 경우가 많다.

🧩 DFS를 잘 쓰는 경우

• 모든 경로를 탐색해야 할 때
• 재귀적으로 문제를 풀기 쉬울 때
• 완전 탐색이 필요한 문제일 때

🧭 구현 포인트

1. 반환값을 전역 변수로 둘지 먼저 정한다.
2. 방문 여부를 저장할 자료구조를 준비한다.
3. 함수의 종료 조건을 명확하게 둔다.
4. 다음 노드를 탐색할 때 재귀 호출 또는 스택을 사용한다.

🧪 Java 샘플 코드

1. 기본 DFS 템플릿

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph;
    static boolean[] visited;

    public static void main(String[] args) {
        int n = 5;
        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        graph[1].add(2);
        graph[1].add(3);
        graph[2].add(4);
        graph[2].add(5);

        dfs(1);
    }

    static void dfs(int node) {
        visited[node] = true;
        System.out.println(node);

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

2. 재귀 호출로 완전 탐색하는 템플릿

public class Main {
    static int answer = 0;

    public static void main(String[] args) {
        dfs("", 0);
        System.out.println(answer);
    }

    static void dfs(String current, int depth) {
        if (depth == 5) {
            answer++;
            return;
        }

        for (char c : new char[] {'A', 'E', 'I', 'O', 'U'}) {
            dfs(current + c, depth + 1);
        }
    }
}

⚠️ 주의사항

• 사이클이 있는 그래프에서는 방문 체크가 필요하다.
• 재귀 호출이 너무 깊어지면 스택 오버플로우가 날 수 있다.

연결문서

• 자료구조