DFS(Depth-First Search) 깊이우선탐색

세하·2025년 5월 25일

DFS 알고리즘

알고리즘

목록 보기

4/5

DFS란?

DFS는 그래프 탐색 알고리즘 중 하나로, "가능한 한 깊이 들어간 후, 막히면 돌아와 다른 경로를 탐색하는" 방식이다.

핵심 원리: LIFO(Last-In, First-Out) 구조인 스택(Stack)을 기반으로 동작한다.
주요 용도: 경로 탐색, 백트래킹(Backtracking), 단절점 찾기, 사이클 탐지, 연결 요소(Connected Components) 확인 등

탐색 순서 예시

아래와 같은 그래프에서 1번 노드부터 탐색을 시작한다고 가정한다.

간선: (1-2), (1-3), (2-4), (3-5)
시작 노드: 1

      1
     / \
    2   3
   /     \
  4       5

1에서 시작한다. (방문: 1)
1과 연결된 2와 3 중 2로 깊게 들어간다. (방문: 1, 2)
2와 연결된 4로 더 깊게 들어간다. (방문: 1, 2, 4)
4는 더 이상 갈 곳이 없다. (막다른 길)
이전 노드인 2로 돌아온다(백트래킹). 2도 4 외에 방문하지 않은 곳이 없으므로 1로 돌아온다.
1에서 아직 방문하지 않은 3으로 탐색을 시작한다. (방문: 1, 2, 4, 3)
3과 연결된 5로 깊게 들어간다. (방문: 1, 2, 4, 3, 5)
5는 더 이상 갈 곳이 없다. 3으로 돌아오고, 1로 돌아오며 탐색이 종료된다.

최종 탐색 순서: 1 → 2 → 4 → 3 → 5

구현 방식: '지도'와 '탐색 도구'의 분리

DFS의 핵심은 그래프(지도)와 탐색 방식(스택)을 분리해서 생각하는 것이다.

📍 그래프 저장 (지도 만들기)

아래 코드의 ArrayList<Integer>[] graph는 DFS 탐색을 위한 '스택'이 아니다.
이것은 노드 간의 연결 상태(간선)를 저장하는 인접 리스트(Adjacency List) 방식으로, 탐색할 '지도' 그 자체이다.

// n+1개의 '방'을 가진 배열(건물)을 만든다.
ArrayList<Integer>[] graph = new ArrayList[n+1];

// 각 '방'을 초기화한다. (List를 넣는다)
for (int i = 1; i <= n; i++){
    graph[i]  = new ArrayList<>();
}

// 1번과 2번이 연결됨 (양방향)
graph[1].add(2);
graph[2].add(1);

📍 탐색 (스택 원리 적용)

지도를 탐색하는 방법은 두 가지이며, 둘 다 본질적으로 스택 원리를 따른다.

① 재귀 함수 (암묵적 스택)
가장 일반적이고 직관적인 구현 방식이다.

static int dfs(int node, ArrayList<Integer>[] graph, boolean[] visited, int count){
    visited[node] = true; // 1. 현재 노드 방문 처리
    count++;

    for (int next : graph[node]) { // 2. 현재 노드와 연결된 노드들 순회
        if (!visited[next]) {     // 3. 아직 방문 안 한 곳이 있다면
            // 4. 즉시 그곳으로 깊게 들어간다 (재귀 호출)
            count = dfs(next, graph, visited, count);
        }
    }
    // 5. (for문이 끝나면) 더 이상 갈 곳이 없으므로 함수가 종료되고,
    //    이전 호출 지점으로 '돌아간다' (백트래킹)
    return count;
}

이 코드에는 Stack 객체가 보이지 않지만, 함수가 자기 자신을 호출(dfs(next, ...) )할 때마다 자바의 호출 스택(Call Stack)이 사용된다.

함수가 호출될 때마다 호출 스택에 "돌아갈 위치"와 "현재 상태"가 쌓인다. (Push)
함수가 return으로 종료되면 스택에서 해당 정보가 빠져나오며 이전 함수로 돌아간다. (Pop)
이 과정이 스택의 LIFO 동작 원리와 완벽히 일치하므로, 재귀 자체가 암묵적인 스택 역할을 수행한다.

② 반복 + 명시적 스택 (Iterative DFS)
재귀가 아닌 Stack 자료구조를 직접 만들어서 구현할 수도 있다.

Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[n+1];

// 1. 시작 노드를 스택에 넣는다.
stack.push(1);
visited[1] = true;

while (!stack.isEmpty()) {
    // 2. 스택의 최상단을 꺼낸다(방문).
    int node = stack.pop();

    // 3. 연결된 노드를 탐색한다.
    for (int next : graph[node]) {
        if (!visited[next]) {
            visited[next] = true;
            // 4. 방문할 곳을 스택에 넣는다 (나중에 방문)
            stack.push(next);
        }
    }
}

인접 리스트로 지도를 그리고, 재귀 함수를 이용해 DFS를 구현한 예시
https://velog.io/@seha01130/백준JAVA-2606번-바이러스

결론

DFS는 스택 원리로 동작한다.
그래프 자체는 인접 리스트(ArrayList[])나 인접 행렬(int[][]) 등으로 저장한다. (지도를 그리는 행위)
탐색은 재귀 함수(암묵적 스택) 또는 Stack 자료구조(명시적 스택)를 이용해 구현한다. (지도를 탐색하는 행위)

➕ 언제 DFS를 재귀로? 반복문으로?

결론부터 말하면, "일단 재귀로 시도하고, 스택 오버플로우가 나면 반복문으로 바꾼다" 가 가장 현실적인 전략이다.
DFS(깊이 우선 탐색)는 본질적으로 '재귀적인' 알고리즘이므로, 재귀로 짜는 것이 훨씬 자연스럽고 코드가 깔끔하다.

1. 재귀 (Recursion) - "일반적인 선택"

재귀는 컴퓨터의 '함수 호출 스택'을 암묵적으로 사용하는 방식이다.

언제 쓰나요?
- 대부분의 경우
- DFS 로직을 처음 구현할 때
- 코드를 짧고, 이해하기 쉽게 짜고 싶을 때
- 그래프의 깊이가 그렇게 깊지 않을 것이라 예상될 때 (예: N이 1,000~10,000 정도)
장점:
- 직관적: "일단 갈 수 있는 데까지 가보고, 막히면 돌아와서 다른 길로 간다"는 DFS의 정의와 코드의 흐름이 정확히 일치
- 간결함: 코드가 매우 짧아짐. 방문 처리를 하고, 다음 노드로 함수를 호출하면 끝이다.
단점:
- 스택 오버플로우 (StackOverflowError): 가장 치명적인 단점. 만약 그래프가 1 -> 2 -> 3 -> ... -> 1,000,000 처럼 한 줄로 매우 길다면, 함수가 100만 번 호출된 채로 쌓이게 된다. 시스템이 정해둔 '함수 호출 스택'의 메모리 한계를 초과하여 프로그램이 터진다.

2. 반복문 + 스택 (Iteration) - "특별한 선택"

반복문은 우리가 Stack 자료구조를 직접 만들어서 '함수 호출 스택'을 흉내 내는 방식이다.

언제 쓰나요?
- 재귀로 풀었더니 스택 오버플로우 에러가 날 때
- 문제의 제약 조건(N)이 100,000을 넘어가는 등 매우 커서, 최악의 경우(일자 그래프) 스택 오버플로우가 명백히 예상될 때
장점:
- 스택 오버플로우가 발생하지 않음: 우리가 직접 만든 Stack은 '힙(Heap)' 메모리 영역을 사용한다. 이 영역은 '함수 호출 스택' 영역보다 훨씬 커서, 웬만한 크기의 데이터는 모두 처리할 수 있다.
단점:
- 복잡함: 코드가 길어지고 직관적이지 않다. 스택에 노드를 push, pop 하고, 방문 처리를 언제 해야 할지(스택에 넣을 때? 뺄 때?) 직접 관리해야 해서 헷갈리기 쉽다.

결론

일단 재귀로 짠다.
- 알고리즘 문제의 90%는 재귀로 짠 DFS로 통과할 수 있다.
- 구현이 빠르고 실수가 적다.
제출해보고 StackOverflowError가 나는지 확인한다.
- 대부분의 코딩 테스트 환경(백준, 프로그래머스 등)은 재귀 깊이(Recursion Depth)에 제한이 있다.
- 보통 이 제한은 1,000 ~ 2,000 정도. 만약 그래프의 깊이가 1,000을 넘어갈 가능성이 있다면 스택 오버플로우가 날 수 있다. (Java는 이보다 더 깊을 수 있지만, 안전하게 생각하는 것이 좋음)
에러가 나면, 그때 가서 반복문 + 스택 버전으로 바꾼다.
- 스택 오버플로우를 확인했다면, 그제야 "아, 이 문제는 재귀의 깊이가 너무 깊어지는 테스트 케이스가 있구나"라고 확신하고 코드를 수정하면 된다.