[알고리즘] DFS 개념 정리 (+ 백준 1260)

2025. 11. 17. 11:35

728x90

🔍 DFS(Depth-First Search) 완전 정복

코딩테스트의 기본 탐색 알고리즘

그래프 탐색 문제를 풀다 보면 DFS(깊이 우선 탐색) 은 반드시 등장하는 핵심 알고리즘.

지금부터 DFS가 무엇인지, 어떤 특징을 가지는지, 어떻게 구현하는지 차근차근 정리해보는 시간을 가져보자.

✅ DFS란?

DFS(Depth-First Search)는 최대한 깊숙한 곳까지 탐색한 뒤 다시 되돌아오는 방식의 탐색 기법

완전탐색(Brute Force)의 한 종류로, 그래프 문제를 해결할 때 가장 많이 사용되는 탐색 방식

✔ 핵심 특징

재귀 함수를 사용해 구현하는 경우가 많음
또는 스택(Stack) 자료구조를 활용
모든 정점을 한 번씩 방문하고 모든 간선을 모두 확인
시간복잡도: O(V + E)
그래프는 보통 인접 리스트로 표현

🧩 동작 방식 시각화 (간단한 이미지 느낌으로 설명)

예를 들어 다음과 같은 그래프가 있다고 가정:

1
├─ 2
│  ├─ 4
│  └─ 5
└─ 3

DFS는 이렇게 방문:

1 → 2 → 4 → (되돌아옴) → 5 → (되돌아옴) → 3

즉, 한 방향으로 끝까지 내려간 뒤 다시 되돌아가서 다른 갈래로 이동하는 방식

⚙ DFS 구현 과정

1. 탐색 준비

그래프를 인접 리스트로 초기화
방문 여부를 표시할 배열 생성
시작 노드를 스택(또는 재귀)로 삽입

2. 스택(또는 재귀 호출)에서 노드를 꺼내기

꺼낸 노드의 인접 노드를 확인해 아직 방문하지 않았다면 스택에 넣는 과정 반복

3. 스택이 empty 상태가 될 때까지 반복

이미 방문한 노드는 다시 방문하지 않음

방문 배열을 활용하여 중복 방문 방지

📘 예제: 백준 1260 DFS/BFS 문제

문제: https://www.acmicpc.net/problem/1260

아래 코드는 DFS와 BFS를 모두 구현한 기본 예제

DFS의 방식이 어떻게 작동하는지 이해하기 좋은 형태

package c5_search.bfs;

import java.util.*;

public class P1260_4 {
    static boolean visited[];
    static ArrayList<Integer>[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int e = sc.nextInt();
        int start = sc.nextInt();

        // 1. 인접리스트 초기화
        arr = new ArrayList[n+1];
        for(int i = 1; i <= n; i++){
            arr[i] = new ArrayList<>();
        }

        // 간선 정보 입력
        for(int i = 0; i < e; i++){
            int first = sc.nextInt();
            int last = sc.nextInt();
            arr[first].add(last);
            arr[last].add(first);
        }

        // 방문 배열 초기화
        visited = new boolean[n+1];

        // 번호가 작은 순서대로 방문하기 위한 정렬
        for(int i = 1; i <= n; i++){
            Collections.sort(arr[i]);
        }

        // DFS 출력
        dfs(start);
        System.out.println();

        // BFS 방문 배열 초기화
        visited = new boolean[n+1];

        // BFS 출력
        bfs(start);
    }

    // DFS (재귀 방식)
    public static void dfs(int node){
        System.out.print(node + " ");
        visited[node] = true;

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

    // BFS (큐 방식)
    public static void bfs(int node){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visited[node] = true;

        while(!queue.isEmpty()){
            int now = queue.poll();
            System.out.print(now + " ");

            for(int next : arr[now]){
                if(!visited[next]){
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }
    }
}

📝 DFS에서 꼭 기억해야 할 포인트

✔ 1. DFS는 재귀 구현이 가장 직관적

재귀 호출 구조가 스택을 그대로 흉내낸 형태

✔ 2. 방문 체크는 가장 먼저 처리

visited[node] = true 를 방문하자마자 수행해야 무한 루프 방지

✔ 3. 그래프는 인접 리스트 사용

인접 리스트가 메모리 절약 + 반복문 처리 효율적

✔ 4. 정렬(Optional)

문제에서 “번호가 작은 순서대로 방문” 조건이 있을 경우 정렬 필수

💡 DFS는 언제 사용할까?

그래프의 한 갈래를 끝까지 탐색해야 하는 문제
모든 경우의 수를 깊게 탐색해야 하는 경우
- 조합/순열 백트래킹
- 미로 탐색
- 연결 요소 찾기
- 트리 구조 탐색

코딩테스트에서 매우 자주 등장하는 유형이므로 반드시 익혀야 하는 기본 알고리즘

📌 마무리

DFS는 알고리즘 문제 풀이의 기초이자, 다양한 문제의 기반이 되는 탐색 알고리즘

재귀, 스택, 인접 리스트 구조에 익숙해진다면 탐색 문제는 훨씬 수월하게 해결 가능