DFS(Depth-First Search)란?
DFS는 깊이 우선 탐색으로 한 경로를 가능한 깊이까지 탐색한 뒤, 더 이상 진행할 수 없으면 이전 단계로 돌아가 다른 경로를 탐색하는 알고리즘이다.
-
특징
- 재귀(Recursion) 또는 스택(Stack)으로 구현 가능
- 모든 경우의 수를 탐색할 때 유용
- 시간 복잡도: O(V+E) (그래프의 경우)
-
사용 사례
- 그래프/트리 탐색
- 미로 찾기
- 모든 경우의 수 탐색(순열, 조합, 부분집합 등)
백트래킹(Backtracking)이란?
백트래킹은 DFS를 기반으로 한 고급 탐색 기법으로 유망하지 않은 경로(해답이 될 수 없는 경우)는 더 깊이 탐색하지 않고 되돌아가는(Backtrack) 기법이다.
-
핵심 아이디어
- 모든 경우의 수를 탐색하면서 조건에 맞지 않으면 즉시 탐색 중단
- Pruning(가지치기)을 통해 불필요한 탐색을 줄인다
-
사용 사례
- N-Queen 문제
- 스도쿠/퍼즐 풀이
- 최적화 문제(최대/최소, 제약 조건 탐색)
- 중복 없는 순열/조합 문제
윷놀이로 보는 DFS & 백트래킹
윷 4개를 던질 때 각 윷은 앞면 또는 뒷면이 나올 수 있다.
총 경우의 수는 2⁴ = 16 가지이다.
| 앞면 개수 | 결과 |
|---|---|
| 0 | 모 |
| 1 | 도 |
| 2 | 개 |
| 3 | 걸 |
| 4 | 윷 |
우리는 DFS를 이용해 모든 경우의 수를 탐색하고 백트래킹을 활용하면 예를 들어 윷(4개 앞면)만 찾는 경우처럼 조건에 맞지 않는 탐색을 생략할 수 있다.
import java.util.Arrays;
public class YutDFS {
static int[] yut = new int[4]; // 0: 뒤, 1: 앞
public static void main(String[] args) {
dfs(0);
}
static void dfs(int idx) {
if (idx == 4) { // 4개 윷을 모두 던짐
int sum = 0;
for (int v : yut) sum += v;
String result = switch (sum) {
case 0 -> "모";
case 1 -> "도";
case 2 -> "개";
case 3 -> "걸";
case 4 -> "윷";
default -> "";
};
System.out.println(Arrays.toString(yut) + " => " + result);
return;
}
// 0(뒷면)
yut[idx] = 0;
dfs(idx + 1);
// 1(앞면)
yut[idx] = 1;
dfs(idx + 1);
}
}출력 예시
[0, 0, 0, 0] => 모
[0, 0, 0, 1] => 도
[0, 0, 1, 0] => 도
...
[1, 1, 1, 0] => 걸
[1, 1, 1, 1] => 윷백트래킹으로 가지치기 예제
예를 들어 윷(4개 앞면)만 찾고 싶다면 이미 던진 앞면 개수가 부족하면 더 이상 탐색하지 않는다.
static void backtracking(int idx, int frontCount) {
// 가지치기: 남은 윷을 전부 앞면으로 던져도 4개가 안 되면 중단
if (frontCount + (4 - idx) < 4) return;
if (idx == 4) {
if (frontCount == 4) {
System.out.println(Arrays.toString(yut) + " => 윷");
}
return;
}
// 뒷면
yut[idx] = 0;
backtracking(idx + 1, frontCount);
// 앞면
yut[idx] = 1;
backtracking(idx + 1, frontCount + 1);
}DFS: 모든 16가지 경우를 다 탐색
백트래킹: 윷을 만들 수 없는 가지는 아예 탐색하지 않음 → 탐색 횟수 줄어듦
심화 예제: 지름길 있는 윷놀이 최소 횟수 탐색
문제
- 0번 칸에서 시작해 20번 칸 이상 도달 시 종료
- 매 턴 윷을 던져 1~4칸 이동
- 특정 칸에는 지름길이 존재하며, 정확히 도착해야만 지름길 사용 가능
- 목표: 최소 횟수로 도착하는 경로 탐색
보드 설계
3번 → 8번, 5번 → 10번 지름길
0 - 1 - 2 - 3* - 4 - 5* - 6 - ... - 20
| |
v v
8 10DFS 탐색
import java.util.*;
public class YutShortcutDFS {
static int minTurn = Integer.MAX_VALUE; // 최소 횟수
static int[] shortcuts = new int[21]; // 지름길 정보
public static void main(String[] args) {
Arrays.fill(shortcuts, -1);
shortcuts[3] = 8; // 3 → 8
shortcuts[5] = 10; // 5 → 10
dfs(0, 0);
System.out.println("최소 횟수: " + minTurn);
}
static void dfs(int pos, int turn) {
if (pos >= 20) { // 도착
minTurn = Math.min(minTurn, turn);
return;
}
for (int move = 1; move <= 4; move++) {
int next = pos + move;
// 지름길 처리
if (next <= 20 && shortcuts[next] != -1) {
next = shortcuts[next];
}
dfs(next, turn + 1);
}
}
}
백트래킹 적용 (Pruning)
DFS로 모든 경로를 탐색하면 4⁵ = 1024 경로를 탐색해야 함.
백트래킹으로 이미 최소 횟수를 초과하는 경로는 중단.
static void backtracking(int pos, int turn) {
if (turn >= minTurn) return; // 가지치기
if (pos >= 20) {
minTurn = Math.min(minTurn, turn);
return;
}
for (int move = 1; move <= 4; move++) {
int next = pos + move;
if (next <= 20 && shortcuts[next] != -1) {
next = shortcuts[next];
}
backtracking(next, turn + 1);
}
}실행 예시
0 → 4 → 8 → 12 → 16 → 20 (5턴)
0 → 3* → 8 → 12 → 16 → 20 (5턴)
0 → 5* → 10 → 14 → 18 → 20 (5턴)
...
최소 횟수: 5DFS vs 백트래킹
| 구분 | DFS | 백트래킹 |
|---|---|---|
| 탐색 범위 | 모든 경로 | 조건에 따라 불필요한 경로 제외 |
| 구현 방식 | 재귀 / 스택 | DFS + 조건 검사 + 가지치기 |
| 사용 사례 | 그래프 탐색, 경우의 수 탐색 | 최적화 문제, 퍼즐, 제약 조건 문제 |
| 장점 | 단순 구현 가능 | 탐색 효율↑ |
📝 느낀점
DFS와 백트래킹의 차이와 활용법을 윷놀이 예제를 통해 직관적으로 이해할 수 있었다. 단순히 DFS를 사용하면 가능한 모든 경우의 수를 탐색할 수 있지만 불필요한 경로까지 전부 확인해야 하므로 탐색 횟수가 많아진다는 단점이 있다. 반면 백트래킹은 DFS에 조건 검사를 더해 유망하지 않은 경로를 조기에 차단함으로써 효율적인 탐색이 가능하다. 윷놀이 예제처럼 간단한 경우에는 차이가 크지 않지만 탐색 공간이 큰 문제일수록 가지치기의 효과가 뚜렷하게 나타난다는 점을 체감했다. 특히 DFS는 순열, 조합, 부분집합과 같은 모든 경우의 수 탐색에 유용하고 백트래킹은 스도쿠, N-Queen, 퍼즐이나 최적화 문제처럼 조건이 있는 탐색 문제에 적합하다는 점을 다시 한 번 정리할 수 있었다. 이번 연습을 통해 문제의 성격에 따라 단순 DFS를 사용할지, 백트래킹으로 가지치기를 적용할지 판단하는 감각을 익힐 수 있었다.
