(코테) [Java] DFS

DFS란?

Depth-First Search, 깊이 우선 탐색은 하나의 경로를 끝까지 탐색한 후 다시 돌아와서 다른 경로를 탐색하는 방식!

• 그래프 탐색에서 많이 사용되며, 스택 또는 재귀 호출로 구현됨
• 특히 트리나 그래프에서 모든 노드나 경로를 탐색해야 하는 문제에 적합함

DFS의 동작 원리

1. 현재 노드를 방문 처리
2. 인접한 노드 중 아직 방문하지 않은 노드를 재귀적으로 방문
3. 더 이상 갈 곳이 없으면 이전 노드로 되돌아감 (Backtracking)

DFS 기본 구조 (재귀)

void dfs(int node) {
    visited[node] = true;

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

예제 1: 인접 리스트 DFS

import java.util.*;

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

    public static void dfs(int node) {
        visited[node] = true;
        System.out.print(node + " ");

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 정점 개수
        int m = sc.nextInt(); // 간선 개수

        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];

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

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u); // 무방향 그래프
        }

        dfs(1); // 1번 정점부터 DFS 시작
    }
}

DFS 탐색 예시

입력 예시 (정점 5, 간선 4):

5 4
1 2
1 3
2 4
3 5

탐색 순서 출력 (시작: 1):

1 2 4 3 5

 

이러한 예시들도 있지만 2차원 배열에서 경로 탐색에서도 사용 가능!

DFS 재귀의 특징

• 재귀함수 호출이 곧 스택처럼 동작
• 방문 여부는 visited 배열로 관리
• 모든 노드를 1번씩만 방문하므로 시간 복잡도는 O(N + M)
• (N: 정점 수, M: 간선 수)

DFS는 언제 사용할까?

상황	이유
모든 경로를 다 탐색해야 할 때	→ 백트래킹 기반 문제
트리 구조에서 특정 조건을 찾을 때	→ ex. 리프 노드, 특정 경로
조합 / 분기 문제	→ ex. 가능한 모든 경우의 수를 구할 때

코테 풀 때 많이 사용했던

1. dfs도 재귀 특징이기 때문에 종료 조건을 잘 둬야했던 방식
2. 문제에서 주어진 배열 크기만큼 visited를 생성하여 true, false로 구분하여 다시 방문 안하게끔 탐색
3. dx = {0,0,1,-1} dy = {1,-1,0,0} 처럼 다음 dfs 이동하는 좌표에 상하좌우를 탐색하는 경우
4. visited 대신에 dp를 활용하여 최소값을 구하는 방식

이렇듯 더 다양한 방식으로 탐색을 추가할 수 있었음

그래서 많이 풀어보고 연습하는게 진짜 좋았던 것 같습니당

정리

• DFS는 "한 길로 끝까지 가보다가 막히면 돌아와서 다시 다른 길로" 탐색하는 방식
• Java에서는 재귀 호출로 가장 자연스럽게 구현 가능
• 백트래킹, 조합, 트리 탐색 등에 아주 많이 사용됨