깊이 우선 탐색 (DFS)

Q: DFS의 시간 복잡도는 얼마인가요?

DFS는 `O(V + E)` 시간에 실행됩니다. 여기서 `V`는 정점 수, `E`는 간선 수이며, 각 정점을 한 번 방문하고 각 간선을 한 번 보기 때문입니다. 스택과 방문 집합에 `O(V)` 공간을 사용합니다.

마지막 업데이트 2026년 7월 1일

깊이 우선 탐색은 되돌아가기 전에 각 분기를 따라 가능한 한 깊이 들어가며 그래프를 탐색합니다. 시작 노드에서 출발하여 한 이웃을 방문하고, 그 이웃의 이웃을 방문하는 식으로 막다른 곳(방문하지 않은 이웃이 없는 노드)에 도달할 때까지 진행하며, 그 시점에 되돌아가 다음 분기를 시도합니다. 위의 재생을 눌러 한 경로를 따라 내려가 바닥에 도달한 뒤 다시 빠져나오는 모습을 확인하세요.

DFS는 스택으로 자연스럽게 표현됩니다. 명시적 스택(여기서 애니메이션으로 보여주는 것)이든 재귀를 통한 호출 스택이든 상관없습니다. 각 노드와 간선을 한 번씩 방문하므로, V개의 정점과 E개의 간선을 가진 그래프에 대해 O(V + E) 시간에 실행됩니다.

시간 및 공간 복잡도

측정 항목	복잡도	비고
시간	O(V + E)	각 정점과 간선을 한 번씩 방문
공간	O(V)	스택 + 방문 집합, 최악의 경우 모든 노드
순회	가장 깊은 것부터	다른 것보다 먼저 한 분기를 끝까지 따라감
자료 구조	스택(또는 재귀)	LIFO 순서가 깊이 우선 동작을 이끎

단계별

단계	무슨 일이 일어나는가
1	시작 노드를 스택에 넣는다.
2	노드를 꺼낸다. 이미 방문했다면 건너뛴다.
3	방문 표시를 하고 그것에 도달한 간선을 기록한다.
4	방문하지 않은 모든 이웃을 스택에 넣는다.
5	스택이 빌 때까지 반복한다.

예제 풀이

그래프 A → [B, C], B → [D], C → [E]에서 A로부터의 반복적 DFS로, 이웃을 나열된 순서대로 넣습니다(LIFO 스택은 가장 나중에 넣은 것을 먼저 꺼냅니다):

단계	스택(오른쪽이 top)	방문	동작
1	`[A]`	`{}`	시작 노드 `A`를 넣는다.
2	`[B, C]`	`{A}`	`A`를 꺼내 방문 표시하고, 이웃 `B` 다음 `C`를 넣는다.
3	`[B, E]`	`{A, C}`	`C`를 꺼내 방문 표시하고, 이웃 `E`를 넣는다.
4	`[B]`	`{A, C, E}`	`E`를 꺼내 방문 표시한다. 이웃 없음.
5	`[D]`	`{A, C, E, B}`	`B`를 꺼내 방문 표시하고, 이웃 `D`를 넣는다.
6	`[]`	`{A, C, E, B, D}`	`D`를 꺼내 방문 표시한다. 스택이 빔: 완료.

DFS를 사용할 때

사용할 때	피할 때
사이클 탐지, 위상 정렬, 또는 연결 요소 찾기가 필요할 때.	가중치 없는 그래프에서 최단 경로가 필요할 때. 이는 DFS가 아니라 BFS가 한다.
그래프가 넓고 얕아서 스택이 많은 프런티어 노드를 담은 큐보다 훨씬 적은 메모리를 쓸 때.	그래프가 매우 깊고 재귀를 사용할 때. 호출 스택이 오버플로될 수 있다.
미로 풀기나 백트래킹 탐색처럼 경로를 완전히 탐색하고 싶을 때.	시작점으로부터의 거리 순서로 노드를 발견해야 할 때.
도달 가능성이나 두 노드 사이에 경로가 존재하는지 확인할 때.	찾은 경로의 간선 수를 최소로 보장해야 할 때.

Depth-First Search 코드

Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Depth-First Search 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.

Python로 구현한 Depth-First Search 코드Python
1def dfs(graph, node, visited):2    visited.add(node)3    order = [node]4    for neighbor in graph[node]:5        if neighbor not in visited:6            order.extend(dfs(graph, neighbor, visited))7    return order8
9
10graph = {11    "A": ["B", "C"],12    "B": ["D", "E"],13    "C": ["F"],14    "D": [],15    "E": ["F"],16    "F": [],17}18
19order = dfs(graph, "A", set())20print("DFS order:", " -> ".join(order))
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Depth-First Search 코드JavaScript
1const graph = {2    A: ["B", "C"],3    B: ["D", "E"],4    C: ["F"],5    D: [],6    E: ["F"],7    F: [],8};9
10function dfs(node, visited = new Set(), order = []) {11    if (visited.has(node)) return order;12    visited.add(node);13    order.push(node);14    for (const next of graph[node]) {15        dfs(next, visited, order);16    }17    return order;18}19
20console.log("DFS from A:", dfs("A").join(" -> "));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Depth-First Search 코드Java
1import java.util.List;2
3public class Main {4    static List<List<Integer>> adj = List.of(5        List.of(1, 2),    // neighbors of 06        List.of(0, 3, 4), // neighbors of 17        List.of(0, 5),    // neighbors of 28        List.of(1),9        List.of(1, 5),10        List.of(2, 4)11    );12    static boolean[] visited = new boolean[6];13
14    static void dfs(int node) {15        visited[node] = true;16        System.out.print(" " + node);17        for (int next : adj.get(node)) {18            if (!visited[next]) dfs(next);19        }20    }21
22    public static void main(String[] args) {23        System.out.print("DFS from 0:");24        dfs(0);25        System.out.println();26    }27}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Depth-First Search 코드C++
1#include <iostream>2#include <vector>3
4void dfs(int node, const std::vector<std::vector<int>>& adj,5         std::vector<bool>& visited) {6    visited[node] = true;7    std::cout << node << " ";8    // Recurse into every unvisited neighbor9    for (int next : adj[node]) {10        if (!visited[next]) dfs(next, adj, visited);11    }12}13
14int main() {15    // 6-node undirected graph as an adjacency list16    std::vector<std::vector<int>> adj = {17        {1, 2},     // 018        {0, 3, 4},  // 119        {0, 5},     // 220        {1},        // 321        {1, 5},     // 422        {2, 4},     // 523    };24    std::vector<bool> visited(adj.size(), false);25    std::cout << "DFS from node 0: ";26    dfs(0, adj, visited);27    std::cout << "\n";28    return 0;29}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Depth-First Search 코드C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6// 6-node undirected graph as an adjacency matrix7int adj[N][N] = {8    {0, 1, 1, 0, 0, 0},9    {1, 0, 0, 1, 1, 0},10    {1, 0, 0, 0, 0, 1},11    {0, 1, 0, 0, 0, 0},12    {0, 1, 0, 0, 0, 1},13    {0, 0, 1, 0, 1, 0},14};15bool visited[N];16
17void dfs(int node) {18    visited[node] = true;19    printf("%d ", node);20    // Recurse into every unvisited neighbor21    for (int next = 0; next < N; next++) {22        if (adj[node][next] && !visited[next]) dfs(next);23    }24}25
26int main(void) {27    printf("DFS from node 0: ");28    dfs(0);29    printf("\n");30    return 0;31}
이 코드를 C 플레이그라운드에서 실행하기

깊이 우선 탐색 자주 묻는 질문

DFS의 시간 복잡도는 얼마인가요?

DFS는 O(V + E) 시간에 실행됩니다. 여기서 V는 정점 수, E는 간선 수이며, 각 정점을 한 번 방문하고 각 간선을 한 번 보기 때문입니다. 스택과 방문 집합에 O(V) 공간을 사용합니다.

DFS와 BFS의 차이는 무엇인가요?

DFS는 스택을 사용해 되돌아가기 전에 한 분기를 따라 깊이 파고들지만, BFS는 큐를 사용해 가까운 노드부터 레벨 단위로 탐색합니다. BFS는 가중치 없는 그래프에서 최단 경로를 찾지만 DFS는 그렇지 않습니다. 다만 DFS는 넓은 그래프에서 메모리를 덜 쓰고, 사이클 탐지와 위상 정렬 같은 작업에 자연스럽습니다.

DFS는 재귀적인가요, 반복적인가요?

둘 다 가능합니다. 재귀 버전은 프로그램의 호출 스택을 암묵적으로 사용해 매우 간결하며, 반복 버전은 명시적 스택(여기의 애니메이션처럼)을 사용해 큰 그래프에서 깊은 재귀로 인한 스택 오버플로를 피합니다.

BFS 대신 DFS를 언제 사용해야 하나요?

경로 전체를 탐색해야 할 때 DFS를 사용하세요. 사이클 탐지, 위상 정렬, 연결 요소, 또는 미로 풀기 같은 백트래킹 탐색 등입니다. 또한 스택이 한 번에 한 분기의 프런티어만 담기 때문에 넓은 그래프에서 메모리도 덜 씁니다. 가중치 없는 그래프에서 최단 경로가 필요하거나 시작점으로부터의 거리 순 노드가 필요할 때는 BFS를 사용하세요.

DFS가 최단 경로를 찾을 수 있나요?

안정적으로는 못 찾습니다. DFS는 우연히 처음 찾은 경로를 반환하는데, 이는 균등하게 확장하기보다 깊이 파고드는 데 전념하기 때문에 종종 간선이 가장 적은 경로가 아닙니다. 가중치 없는 그래프의 최단 경로에는 BFS를, 가중치 있는 그래프에는 Dijkstra 알고리즘을 사용하세요.

DFS는 왜 방문 집합이 필요한가요?

방문 집합이 없으면 DFS는 여러 경로로 도달할 수 있는 노드를 다시 방문하고, 사이클이 있는 그래프에서는 영원히 반복합니다. 노드를 꺼낼 때 방문 표시를 하고(이미 방문한 꺼내기는 건너뛰면) 각 노드가 한 번만 처리되도록 보장되어 실행 시간이 O(V + E)로 유지됩니다. 흔한 실수는 꺼낼 때만 노드를 방문 표시하면서 중복을 계속 넣는 것인데, 이는 올바르지만 건너뛰어야 할 오래된 항목이 스택에 남을 수 있습니다.