[알고리즘] 28. DFS 깊이 우선 탐색
지난 글에서는 이분 탐색 응용에 대해 정리했습니다. 이번 글에서는 그래프 탐색에서 매우 자주 등장하는 DFS에 대해 알아보겠습니다.
DFS는 Depth First Search의 줄임말로, 우리말로는 깊이 우선 탐색이라고 합니다. 이름 그대로 한 방향으로 갈 수 있는 곳까지 깊게 들어간 뒤, 더 이상 갈 곳이 없으면 되돌아와 다른 방향을 탐색하는 방식입니다.
DFS는 한 방향으로 깊게 탐색한 뒤, 막히면 되돌아와 다른 경로를 탐색하는 알고리즘입니다.
1. DFS란?
DFS는 그래프나 트리에서 모든 정점을 방문할 때 사용하는 탐색 방법입니다. 특정 시작점에서 출발해 연결된 정점을 따라 최대한 깊게 이동합니다.
1
├─ 2
│ ├─ 4
│ └─ 5
└─ 3위와 같은 구조에서 1번부터 DFS를 시작하면 보통 다음 순서로 방문할 수 있습니다.
1 → 2 → 4 → 5 → 3먼저 1에서 2로 이동하고, 2에서 다시 4로 깊게 들어갑니다. 4에서 더 이상 갈 곳이 없으면 다시 2로 돌아와 5를 탐색합니다. 그 후 1로 돌아와 3을 탐색합니다.
DFS의 핵심은 가능한 한 깊게 들어가고, 막히면 되돌아오는 것입니다.
2. DFS가 필요한 상황
DFS는 연결 관계를 따라 깊게 탐색해야 하는 문제에서 자주 사용됩니다.
- 그래프의 모든 정점 방문하기
- 연결된 영역의 개수 세기
- 경로가 존재하는지 확인하기
- 미로 탐색
- 섬의 개수 구하기
- 트리 순회
- 백트래킹 문제
문제를 보고 “연결된 곳을 따라 끝까지 가봐야 한다”는 느낌이 들면 DFS를 떠올릴 수 있습니다.
3. DFS의 기본 흐름
DFS의 기본 흐름은 다음과 같습니다.
- 시작 정점을 방문 처리한다.
- 현재 정점과 연결된 정점을 확인한다.
- 아직 방문하지 않은 정점이 있다면 그 정점으로 이동한다.
- 이동한 정점에서도 같은 과정을 반복한다.
- 더 이상 갈 곳이 없으면 이전 정점으로 돌아간다.
방문 처리
→ 연결된 정점 확인
→ 방문하지 않았다면 이동
→ 더 이상 갈 곳이 없으면 되돌아감DFS는 보통 재귀 함수를 이용해 구현합니다. 재귀 호출 자체가 “들어갔다가 돌아오는” 구조를 자연스럽게 표현하기 때문입니다.
DFS는 재귀와 잘 어울리는 탐색 방식입니다.
4. 방문 배열이 필요한 이유
그래프에는 사이클이 있을 수 있습니다. 따라서 이미 방문한 정점을 다시 방문하지 않도록 visited 배열이 필요합니다.
1 --- 2
| |
3 --- 4위 그래프에서 방문 체크를 하지 않으면 1 → 2 → 4 → 3 → 1처럼 다시 처음 정점으로 돌아올 수 있습니다. 이 과정이 반복되면 탐색이 끝나지 않을 수 있습니다.
그래서 정점을 방문하면 visited 값을 true로 바꿔야 합니다.
boolean[] visited = new boolean[n + 1];
visited[1] = true;DFS에서는 이미 방문한 정점을 다시 방문하지 않도록 반드시 방문 체크를 해야 합니다.
5. 인접 리스트로 그래프 만들기
DFS를 구현하기 전에 그래프의 연결 정보를 저장해야 합니다. 정점 수가 많을 때는 보통 인접 리스트를 사용합니다.
다음 그래프를 생각해보겠습니다.
1 --- 2
| |
3 --- 4연결 관계는 다음과 같습니다.
| 정점 | 연결된 정점 |
|---|---|
| 1 | 2, 3 |
| 2 | 1, 4 |
| 3 | 1, 4 |
| 4 | 2, 3 |
Java에서는 ArrayList 배열로 인접 리스트를 만들 수 있습니다.
import java.util.ArrayList;
int n = 4;
ArrayList<Integer>[] graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
graph[1].add(2);
graph[2].add(1);
graph[1].add(3);
graph[3].add(1);
graph[2].add(4);
graph[4].add(2);
graph[3].add(4);
graph[4].add(3);무방향 그래프이므로 양쪽 방향을 모두 저장했습니다.
6. DFS 재귀 기본 코드
DFS의 가장 기본적인 재귀 코드는 다음과 같습니다.
static ArrayList<Integer>[] graph;
static boolean[] visited;
public static void dfs(int current) {
visited[current] = true;
System.out.println(current);
for (int next : graph[current]) {
if (!visited[next]) {
dfs(next);
}
}
}코드 흐름은 다음과 같습니다.
- 현재 정점을 방문 처리한다.
- 현재 정점을 출력한다.
- 현재 정점과 연결된 정점을 하나씩 확인한다.
- 아직 방문하지 않은 정점이면 dfs를 다시 호출한다.
재귀 호출을 통해 연결된 정점으로 계속 깊게 들어갑니다.
7. DFS 전체 예제 코드
이번에는 그래프 생성부터 DFS 실행까지 전체 코드를 보겠습니다.
import java.util.ArrayList;
public class Main {
static ArrayList<Integer>[] graph;
static boolean[] visited;
public static void main(String[] args) {
int n = 4;
graph = new ArrayList[n + 1];
visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(3, 4);
dfs(1);
}
public static void addEdge(int a, int b) {
graph[a].add(b);
graph[b].add(a);
}
public static void dfs(int current) {
visited[current] = true;
System.out.println(current);
for (int next : graph[current]) {
if (!visited[next]) {
dfs(next);
}
}
}
}출력 순서는 인접 리스트에 값을 넣은 순서에 따라 달라질 수 있습니다. 위 코드에서는 다음과 같이 출력됩니다.
1
2
4
31에서 시작해 2로 깊게 들어가고, 2에서 4로 이동한 뒤, 4와 연결된 3을 방문합니다.
DFS 방문 순서는 연결 정보를 어떤 순서로 저장했는지에 따라 달라질 수 있습니다.
8. DFS 동작 과정 예시
아래 그래프에서 1번 정점부터 DFS를 시작한다고 생각해보겠습니다.
1 --- 2
| |
3 --- 4인접 리스트가 다음 순서라고 가정하겠습니다.
1: 2, 3
2: 1, 4
3: 1, 4
4: 2, 3DFS 동작 흐름은 다음과 같습니다.
| 단계 | 현재 정점 | 동작 |
|---|---|---|
| 1 | 1 | 1 방문, 2로 이동 |
| 2 | 2 | 2 방문, 4로 이동 |
| 3 | 4 | 4 방문, 3으로 이동 |
| 4 | 3 | 3 방문, 더 갈 곳 없음 |
방문 순서는 1 → 2 → 4 → 3입니다. 중간에 이미 방문한 정점은 다시 방문하지 않습니다.
9. DFS와 스택의 관계
DFS는 재귀로 구현하는 경우가 많지만, 사실 내부적으로는 스택 구조와 관련이 있습니다. 재귀 호출은 호출 정보를 스택처럼 쌓아두기 때문입니다.
dfs(1)
dfs(2)
dfs(4)
dfs(3)가장 깊게 들어간 dfs(3)이 끝나면 dfs(4)로 돌아오고, 그다음 dfs(2), dfs(1) 순서로 되돌아갑니다. 이 흐름이 스택의 후입선출 구조와 비슷합니다.
DFS는 재귀를 사용하면 자연스럽게 스택처럼 동작합니다.
10. 스택으로 DFS 구현하기
DFS는 재귀 대신 직접 Stack을 사용해서 구현할 수도 있습니다.
import java.util.ArrayList;
import java.util.Stack;
public static void dfsWithStack(int start) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int current = stack.pop();
if (visited[current]) {
continue;
}
visited[current] = true;
System.out.println(current);
for (int next : graph[current]) {
if (!visited[next]) {
stack.push(next);
}
}
}
}스택을 사용하면 재귀 호출 없이도 DFS를 구현할 수 있습니다. 다만 방문 순서는 재귀 방식과 다르게 나올 수 있습니다. 스택은 마지막에 넣은 정점부터 꺼내기 때문입니다.
11. DFS로 연결 요소 개수 세기
DFS는 그래프에서 연결된 그룹의 개수를 셀 때도 자주 사용됩니다. 이런 그룹을 연결 요소라고 부릅니다.
1 --- 2 3 --- 4 5위 그래프에는 연결 요소가 3개 있습니다.
- {1, 2}
- {3, 4}
- {5}
모든 정점을 돌면서 아직 방문하지 않은 정점에서 DFS를 시작하면 연결 요소 개수를 셀 수 있습니다.
int count = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i);
count++;
}
}
System.out.println(count);새로운 DFS가 시작될 때마다 새로운 연결 요소를 발견한 것입니다.
연결 요소 개수는 방문하지 않은 정점에서 DFS를 몇 번 시작하는지로 구할 수 있습니다.
12. 2차원 배열에서 DFS
DFS는 그래프뿐 아니라 2차원 배열에서도 자주 사용됩니다. 대표적인 예가 지도, 미로, 섬의 개수 문제입니다.
1 1 0
0 1 0
0 0 1여기서 1은 땅, 0은 바다라고 생각할 수 있습니다. 상하좌우로 연결된 1들을 하나의 영역으로 보고 DFS를 수행할 수 있습니다.
2차원 배열에서는 보통 이동 방향 배열을 사용합니다.
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};위 배열은 상, 하, 좌, 우 이동을 의미합니다.
13. 2차원 DFS 기본 코드
2차원 배열에서 DFS를 구현하면 다음과 같습니다.
static int[][] map;
static boolean[][] visited;
static int n;
static int m;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void dfs(int x, int y) {
visited[x][y] = true;
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
if (visited[nx][ny]) {
continue;
}
if (map[nx][ny] == 0) {
continue;
}
dfs(nx, ny);
}
}2차원 DFS에서는 범위 체크가 매우 중요합니다. 배열 밖으로 나가면 오류가 발생하기 때문입니다.
2차원 DFS에서는 방문 체크보다 먼저 배열 범위를 확인해야 합니다.
14. DFS의 시간복잡도
그래프 DFS는 모든 정점과 간선을 한 번씩 확인합니다. 정점 수를 V, 간선 수를 E라고 하면 시간복잡도는 보통 O(V + E)입니다.
| 구분 | 의미 |
|---|---|
| V | 정점의 개수 |
| E | 간선의 개수 |
| DFS 시간복잡도 | O(V + E) |
2차원 배열 DFS에서는 모든 칸을 한 번씩 방문한다고 보면 됩니다. 행의 개수를 N, 열의 개수를 M이라고 하면 시간복잡도는 O(N × M)입니다.
DFS는 방문 체크를 제대로 하면 각 정점이나 칸을 보통 한 번씩만 방문합니다.
15. DFS에서 자주 하는 실수
DFS 문제를 풀 때는 아래 실수를 조심해야 합니다.
- 방문 배열을 사용하지 않는 경우
- 방문 처리를 재귀 호출 이후에 하는 경우
- 무방향 그래프에서 간선을 한쪽만 저장하는 경우
- 2차원 배열에서 범위 체크를 하지 않는 경우
- 이미 방문한 위치를 다시 탐색하는 경우
- 재귀 종료 조건을 제대로 작성하지 않는 경우
- 연결 그래프가 아닌데 시작점 하나에서만 DFS를 실행하는 경우
특히 방문 처리는 DFS에 들어가자마자 바로 하는 것이 안전합니다.
public static void dfs(int current) {
visited[current] = true;
for (int next : graph[current]) {
if (!visited[next]) {
dfs(next);
}
}
}DFS 실수의 대부분은 방문 체크와 범위 체크에서 발생합니다.
16. 정리
이번 글에서는 DFS에 대해 정리했습니다.
- DFS는 깊이 우선 탐색이다.
- 한 방향으로 갈 수 있는 곳까지 깊게 탐색한 뒤 되돌아온다.
- DFS는 재귀 또는 스택으로 구현할 수 있다.
- 그래프 탐색에서는 방문 배열이 반드시 필요하다.
- 인접 리스트를 사용하면 그래프 연결 정보를 효율적으로 저장할 수 있다.
- 연결 요소 개수 세기, 경로 탐색, 미로 탐색, 섬의 개수 문제에 자주 사용된다.
- 그래프 DFS의 시간복잡도는 O(V + E)이다.
- 2차원 배열 DFS에서는 범위 체크와 방문 체크가 중요하다.
DFS는 그래프 탐색의 기본이 되는 알고리즘입니다. 처음에는 재귀 흐름이 헷갈릴 수 있지만, 현재 위치를 방문하고 연결된 다음 위치로 깊게 들어간다는 흐름을 잡으면 다양한 문제에 응용할 수 있습니다.
DFS의 핵심은 방문하지 않은 곳으로 깊게 들어가고, 더 이상 갈 곳이 없으면 되돌아오는 것입니다.
다음 글 예고
다음 글에서는 BFS에 대해 알아보겠습니다.
가까운 정점부터 차례대로 탐색하는 방식, 큐를 이용한 BFS 구현, 최단 거리 문제에서 BFS가 사용되는 이유를 예제로 정리해보겠습니다.
'Problem Solving > Algorithm' 카테고리의 다른 글
| [알고리즘] 30. 방문 배열 (0) | 2026.07.13 |
|---|---|
| [알고리즘] 29. BFS 너비 우선 탐색 (0) | 2026.07.12 |
| [알고리즘] 27. 이분 탐색 응용 (0) | 2026.07.10 |
| [알고리즘] 26. 이분 탐색 기초 (0) | 2026.07.09 |
| [알고리즘] 25. 선형 탐색(Linear Search) (0) | 2026.07.09 |