[알고리즘] DFS(깊이 우선 탐색)란? (백준 11724, 2667)

📌 핵심 요약

• DFS(깊이 우선 탐색)는 한 방향으로 갈 수 있는 만큼 끝까지 파고든 뒤, 막히면 되돌아와 다른 길을 탐색하는 알고리즘입니다.
• “되돌아오기”를 구현하기 위해 스택(Stack) 또는 재귀 호출을 사용하며, 실전에서는 재귀 방식이 훨씬 간결합니다.
• 최단 거리는 보장하지 않지만, 연결 요소 찾기 · 모든 경로 탐색 · 백트래킹의 기반이 되는 필수 알고리즘입니다.
• 백준 11724(연결 요소의 개수), 2667(단지번호붙이기) 두 문제로 그래프 DFS와 2차원 격자 DFS를 직접 풀어봅니다.

 

목차

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

DFS(Depth-First Search, 깊이 우선 탐색)는 그래프나 트리에서 한 방향으로 갈 수 있는 만큼 깊이 파고들며 탐색하는 알고리즘입니다. 미로에서 길을 찾는 사람을 떠올리면 됩니다. 갈림길이 나오면 일단 한쪽 길을 선택해 막다른 곳이 나올 때까지 걸어가고, 막히면 마지막 갈림길로 되돌아와서 아직 가보지 않은 다른 길을 시도합니다. 이 과정을 반복하면 결국 미로의 모든 길을 한 번씩 밟게 됩니다.

BFS가 “가까운 곳부터 한 겹씩” 넓게 퍼져나갔다면, DFS는 “일단 한 길로 끝까지” 깊게 들어간다는 점이 정반대입니다.

스택(Stack)이란?

스택(Stack)은 나중에 넣은 데이터가 먼저 나오는(LIFO, Last-In First-Out) 자료구조입니다. 접시를 쌓아둔 더미처럼, 꺼낼 때는 항상 맨 위(가장 최근에 올린 접시)부터 꺼냅니다.

DFS에 스택이 필요한 이유는 “가장 최근에 지나온 갈림길”로 되돌아가야 하기 때문입니다. 지나온 갈림길을 스택에 차곡차곡 쌓아두면, 막다른 길을 만났을 때 스택의 맨 위를 꺼내는 것만으로 가장 최근 갈림길로 돌아갈 수 있습니다.

BFS가 “먼저 발견한 것 먼저”를 위해 큐를 썼다면, DFS는 “가장 최근 것부터 되짚기”를 위해 스택을 씁니다.

왜 재귀 호출로 구현할까?

재귀 호출(Recursion)은 메서드가 자기 자신을 다시 호출하는 방식입니다.

그런데 사실 자바는 메서드를 호출할 때마다 호출 정보를 콜 스택(Call Stack)이라는 내부 스택에 자동으로 쌓고, 메서드가 끝나면 꺼내서 이전 위치로 돌아갑니다.

즉 재귀 호출을 쓰면 “되돌아오기”에 필요한 스택 관리를 자바가 대신 해주는 셈입니다. 그래서 실전에서는 스택을 직접 다루는 코드보다 재귀 방식이 훨씬 짧고 직관적이라 대부분 재귀로 DFS를 구현합니다.

ℹ️

큐를 쓰면 BFS, 스택(재귀)을 쓰면 DFS

두 알고리즘의 코드 구조는 거의 같습니다. “다음에 방문할 노드”를 큐로 관리하면 BFS, 스택(또는 재귀)으로 관리하면 DFS가 됩니다. 자료구조 하나의 차이가 탐색 순서 전체를 바꾼다는 점이 두 알고리즘의 핵심입니다.

2 DFS의 동작 원리

재귀 기준으로 DFS의 전체 흐름은 아래 4단계입니다. “방문 → 더 깊이 → 막히면 복귀”의 반복이라고 기억하면 됩니다.

DFS 동작 4단계 (재귀 기준)

1. 시작 노드에서 dfs 메서드를 호출하고, 진입하자마자 방문 처리(visited = true)합니다.
2. 현재 노드와 연결된 인접 노드를 확인해, 아직 방문하지 않은 노드가 있으면 그 노드로 dfs를 재귀 호출합니다. (더 깊이 파고들기)
3. 인접 노드를 전부 방문했다면(막다른 길) 메서드가 종료되고, 자동으로 이전 노드로 되돌아갑니다. (백트래킹)
4. 되돌아온 노드에서 남은 다른 인접 노드에 대해 2~3번을 반복합니다. 최초 호출까지 종료되면 시작점에서 도달 가능한 모든 노드를 방문한 것입니다.

⚠️

방문 처리를 빠뜨리면 무한 재귀에 빠집니다

그래프에 사이클(순환 경로)이 있을 때 방문 처리를 하지 않으면, 두 노드가 서로를 계속 재귀 호출하다가 StackOverflowError(콜 스택이 가득 차서 발생하는 에러)로 프로그램이 죽습니다. dfs 메서드에 진입하자마자 방문 처리하는 것을 습관으로 만드세요.

3 DFS vs BFS 비교

두 알고리즘 모두 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(V + E)로 같습니다. (V = 노드 수, E = 간선 수) 어떤 문제에서 어느 쪽을 골라야 하는지가 실전의 핵심입니다.

구분	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
탐색 방식	한 방향으로 끝까지 파고든 후 되돌아옴	가까운 노드부터 한 겹씩 확장
사용 자료구조	스택 (Stack) 또는 재귀	큐 (Queue)
최단 거리 보장	보장 안 됨	보장 (가중치 없을 때)
구현 난이도	재귀로 매우 간결	큐 관리 코드 필요
주의할 점	깊은 재귀 시 스택 오버플로우	큐 중복 삽입 시 메모리 초과
유리한 문제	연결 요소, 모든 경로 탐색, 백트래킹, 사이클 판별	최단 거리, 최소 횟수, 가까운 대상 찾기

💡

“몇 개인가 / 모든 경우”는 DFS, “최단 · 최소”는 BFS

연결된 덩어리가 몇 개인지 세거나, 가능한 모든 경우를 탐색하는 문제는 구현이 간결한 DFS가 편합니다. 반면 “최단 거리”, “최소 횟수”가 등장하면 BFS를 선택하세요. 단순히 모든 노드를 방문하기만 하면 되는 문제(연결 요소 등)는 둘 중 아무거나 써도 정답이 같습니다.

4 Java로 DFS 구현하기

그래프는 BFS 때와 마찬가지로 인접 리스트(각 노드마다 “연결된 노드 목록”을 저장하는 방식)로 표현합니다. 먼저 가장 많이 쓰는 재귀 버전입니다. 큐 관리 코드가 없어서 BFS보다 훨씬 짧다는 점을 확인해 보세요.

 

Java — DFS 기본 템플릿 (재귀)

import java.util.*;

public class DfsTemplate {

    // graph[i] = i번 노드와 연결된 노드 목록 (인접 리스트)
    static List<Integer>[] graph;
    static boolean[] visited;

    static void dfs(int cur) {
        // 1. 진입하자마자 방문 처리 (무한 재귀 방지!)
        visited[cur] = true;
        System.out.println("방문: " + cur);

        // 2. 미방문 인접 노드로 더 깊이 파고든다
        for (int next : graph[cur]) {
            if (!visited[next]) {
                dfs(next);
            }
        }
        // 3. for문이 끝나면(막다른 길) 자동으로 이전 노드로 복귀
    }
}

같은 동작을 스택으로 직접 구현하면 아래와 같습니다. 재귀가 내부적으로 어떤 일을 하는지 이해하는 데 도움이 되고, 재귀 깊이 제한에 걸릴 만큼 그래프가 깊을 때의 대안이 되기도 합니다.

 

Java — DFS 스택 버전 (참고용)

static void dfsWithStack(int start) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);

    while (!stack.isEmpty()) {
        int cur = stack.pop(); // 맨 위(가장 최근)부터 꺼낸다
        if (visited[cur]) continue;
        visited[cur] = true;
        System.out.println("방문: " + cur);

        for (int next : graph[cur]) {
            if (!visited[next]) stack.push(next);
        }
    }
}

ℹ️

자바에서 스택은 ArrayDeque를 권장합니다

자바에는 Stack 클래스가 있지만 오래된 설계(모든 메서드에 동기화 처리)로 성능이 떨어져, 공식 문서에서도 Deque 인터페이스와 ArrayDeque 구현체 사용을 권장합니다. push()로 맨 위에 넣고 pop()으로 맨 위에서 꺼냅니다.

5 문제풀이 1 : 백준 11724 연결 요소의 개수

첫 번째 문제는 DFS 입문의 정석인 연결 요소의 개수입니다. 연결 요소(Connected Component)란 그래프 안에서 서로 오갈 수 있는 노드들의 덩어리를 말합니다. 이 문제의 핵심은 “모든 노드에 대해 DFS 시도 → 새로 탐색이 시작된 횟수 = 덩어리 수”라는 패턴입니다.

BOJ #11724

연결 요소의 개수

N ≤ 1,000 · M ≤ N×(N-1)/2 · 시간제한 3초

난이도: Silver V

방향 없는 그래프가 주어졌을 때, 연결 요소(서로 연결된 노드 덩어리)의 개수를 출력하는 문제입니다.

풀이 과정

1. 간선이 양방향이므로 인접 리스트에 양쪽 모두 간선을 추가해 그래프를 만든다.
2. 1번부터 N번까지 모든 노드를 순회하면서, 아직 방문하지 않은 노드를 만나면 그 노드에서 DFS를 시작한다.
3. DFS 한 번이 끝나면 연결된 덩어리 하나를 전부 방문한 것이므로, DFS를 새로 시작한 횟수가 곧 연결 요소의 개수다.

 

Java — 백준 11724 연결 요소의 개수

import java.io.*;
import java.util.*;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 노드 수
        int m = Integer.parseInt(st.nextToken()); // 간선 수

        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++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }

        // 모든 노드를 순회하며, 미방문 노드에서 DFS 시작
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfs(i);
                count++; // 새 덩어리 발견!
            }
        }

        System.out.println(count);
    }

    static void dfs(int cur) {
        visited[cur] = true;
        for (int next : graph[cur]) {
            if (!visited[next]) dfs(next);
        }
    }
}

💡

“모든 노드 순회 + 미방문 시 DFS” 패턴을 기억하세요

BFS의 바이러스(2606)는 시작점 하나에서 탐색했지만, 이 문제처럼 그래프가 여러 덩어리로 나뉘어 있을 수 있는 경우에는 모든 노드를 for문으로 순회하며 미방문 노드마다 새로 탐색을 시작해야 합니다. 다음 문제인 단지번호붙이기도 똑같은 패턴입니다.

6 문제풀이 2 : 백준 2667 단지번호붙이기

두 번째 문제는 2차원 격자 DFS의 대표 문제인 단지번호붙이기입니다.

방금 배운 “모든 노드 순회 + 미방문 시 DFS” 패턴을 격자에 적용하고, 추가로 DFS의 반환값으로 덩어리의 크기를 누적하는 기법을 배웁니다. 격자에서 상하좌우 이동은 BFS 때와 동일하게 방향 배열(dx, dy)을 사용합니다.

BOJ #2667

단지번호붙이기

지도 크기 N ≤ 25 · 시간제한 1초

난이도: Silver I

N×N 지도에서 1은 집, 0은 빈 땅입니다. 상하좌우로 붙어 있는 집들을 하나의 단지로 묶을 때, 총 단지 수와 각 단지의 집 수를 오름차순으로 출력하는 문제입니다.

풀이 과정

1. 지도의 모든 칸을 이중 for문으로 순회하다가, 집(1)이면서 미방문인 칸을 만나면 그 칸에서 DFS를 시작한다. (= 새 단지 발견)
2. DFS는 현재 칸을 방문 처리한 뒤, 상하좌우의 범위 안 · 집 · 미방문 칸으로 재귀를 이어간다.
3. DFS가 “자기 자신 1채 + 재귀로 이어진 집들의 수”를 반환하도록 만들면, 최초 호출의 반환값이 곧 그 단지의 집 수가 된다.
4. 단지별 집 수를 리스트에 모아 오름차순 정렬 후, 단지 수와 함께 출력한다.

 

Java — 백준 2667 단지번호붙이기

import java.io.*;
import java.util.*;

public class Main {
    // 상, 하, 좌, 우 네 방향
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n;
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine().trim());
        map = new int[n][n];
        visited = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }

        // 모든 칸 순회 : 집(1)이면서 미방문이면 새 단지
        List<Integer> sizes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    sizes.add(dfs(i, j)); // 단지 하나 통째로 탐색
                }
            }
        }

        // 오름차순 정렬 후 출력
        Collections.sort(sizes);
        StringBuilder sb = new StringBuilder();
        sb.append(sizes.size()).append('\n');
        for (int s : sizes) sb.append(s).append('\n');
        System.out.print(sb);
    }

    // 반환값 = 이 칸에서 이어진 단지의 집 수
    static int dfs(int x, int y) {
        visited[x][y] = true;
        int size = 1; // 자기 자신 1채

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            // 지도 범위 밖이면 건너뛰기
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            // 빈 땅(0)이거나 이미 방문한 칸이면 건너뛰기
            if (map[nx][ny] == 0 || visited[nx][ny]) continue;

            size += dfs(nx, ny); // 이어진 집 수를 누적
        }
        return size;
    }
}

⚠️

재귀 DFS는 격자가 크면 StackOverflowError가 날 수 있습니다

이 문제는 지도가 최대 25×25 = 625칸이라 재귀 깊이가 얕아 안전합니다. 하지만 격자가 수백×수백처럼 커지면 재귀 깊이가 수만~수십만까지 깊어져 콜 스택이 넘칠 수 있습니다. 그럴 때는 스택 버전 DFS로 바꾸거나 BFS로 대체하는 것이 안전합니다. 이 판단 기준을 알아두면 실전에서 큰 도움이 됩니다.

7 마무리

DFS의 핵심을 다시 정리하면 세 가지입니다.

한 길로 끝까지 파고들고, 막히면 되돌아온다, 재귀 호출이 콜 스택을 통해 “되돌아오기”를 자동으로 처리해 준다, dfs 진입 즉시 방문 처리한다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.