백트래킹(Backtracking)에 대해 공부 후 정리하였습니다.
Summary
- 백트래킹은 완전탐색을 효율적으로 줄이는 기법
- DFS + Pruning 구조로 구현
- 시간복잡도는 최악은 지수적이지만, 가지치기로 충분히 줄어듦
- 코딩테스트에서 순열, 조합, 스도쿠, N-Queens, 경로 탐색 등에 많이 등장
1️⃣ 백트래킹(Backtracking)의 개념
모든 경우의 수를 탐색하는 DFS 기반의 완전 탐색 기법이지만, 조건에 맞지 않는 경우는 탐색을 조기에 중단(Pruning, 가지치기) 하여 탐색 공간을 줄이는 방법
즉, “해가 될 수 없는 부분은 탐색하지 않고 되돌아감” → 불필요한 탐색을 줄여 효율적으로 문제 해결 가능
2️⃣ 특징
- 완전 탐색 기반 → 최악의 경우 시간 복잡도는 여전히 지수적
- 하지만 가지치기(Pruning) 로 탐색 공간을 줄여 효율적으로 해결
- 주로 재귀 함수(DFS)로 구현
- 대표적으로 순열, 조합, N-Queens, 부분 집합, 그래프 경로 탐색 문제에 사용
3️⃣ 시간 복잡도
가늠하기 어려움
일반적으로 O(지수 시간, 예: N!), Pruning 정도에 따라 실질적인 시간은 훨씬 줄어듦
- N-Queens의 최악은 O(N!), 하지만 Pruning을 잘 하면 더 빠름
- 부분 집합 탐색: O(2^N)
4️⃣ 구현 방법
- DFS(재귀)로 상태 공간을 탐색
- 현재 상태에서 해가 될 수 없는 경우는 가지치기 (return)
- 가능한 경우에만 다음 단계로 진행
- 목표 지점까지 도달하면 해(solution) 저장
5️⃣ 기본 코드 예시
순열 생성 (N개의 수 중 N개 선택)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.io.*;
import java.util.*;
public class Main {
static int N = 3;
static int[] list = {1, 2, 3};
static boolean[] visited = new boolean[N];
static int[] arr = new int[N];
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
func(0);
System.out.println(sb);
}
static void func(int k) { // 현재 k개까지 수를 택했음
if(index == N) { // N개를 모두 택했으면
for(int i = 0; i < N; i++) {
sb.append(arr[i]).append(" "); // arr에 기록해둔 수를 출력
}
sb.append('\n');
return;
}
for(int i = 0; i < N; i++) { // list안의 N개의 수에 대해
if(!visited[i]) { // 아직 list[i]가 사용되지 않았으면
arr[k] = list[i]; // k번째 수를 list[i]로 정함
visited[i] = true; // list[i]를 사용되었다고 표시
func(k + 1); // 다음 수를 정하러 한 단계 더 들어감
visited[i] = false; // k번째 수를 list[i]로 정한 모든 경우에 대해 다 확인했으니 list[i]를 이제 사용되지않았다고 명시
}
}
}
N-Queen
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Scanner;
public class Main {
static boolean[] isused1 = new boolean[40]; // column 차지 여부
static boolean[] isused2 = new boolean[40]; // / 방향 대각선 차지 여부
static boolean[] isused3 = new boolean[40]; // \ 방향 대각선 차지 여부
static int cnt = 0;
static int n;
static void func(int cur) { // cur번째 row에 퀸 배치할 예정
if (cur == n) { // N개 다 배치 성공
cnt++;
return;
}
for (int i = 0; i < n; i++) { // (cur, i)에 퀸 배치 시도
if (isused1[i] || isused2[i + cur] || isused3[cur - i + n - 1])
continue;
isused1[i] = true;
isused2[i + cur] = true;
isused3[cur - i + n - 1] = true;
func(cur + 1);
isused1[i] = false;
isused2[i + cur] = false;
isused3[cur - i + n - 1] = false;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
func(0);
System.out.println(cnt);
}
}
부분수열의 합
- 부분합을 고르는 것과 동일한 상황 (공집합 제외 2^n - 1개 부분집합 확인) ```java import java.util.Scanner;
public class Main { static int n, s; // 원소 개수 n, 목표 합 s static int[] arr; // 입력 배열 static int cnt = 0; // 조건을 만족하는 부분수열 개수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// cur: 현재 탐색 중인 원소의 인덱스
// tot: 지금까지 선택한 원소들의 합
static void func(int cur, int tot) {
// 기저 조건: 배열 끝까지 탐색한 경우
if (cur == n) {
if (tot == s) cnt++; // 합이 목표 s라면 개수 증가
return;
}
// 현재 원소를 선택하지 않는 경우
func(cur + 1, tot);
// 현재 원소를 선택하는 경우
func(cur + 1, tot + arr[cur]);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
s = sc.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
func(0, 0);
// 공집합은 문제 조건에서 제외해야 하므로 s==0이면 1 빼줌
if (s == 0) cnt--;
System.out.println(cnt);
} } ```
6️⃣ 자주 사용하는 곳
- 순열, 조합, 부분집합 탐색
- N-Queens, 스도쿠
- 그래프 경로 탐색 (Hamiltonian Path, Traveling Salesman Problem)
- 퍼즐 문제 (예: 미로 찾기, 체스 나이트 투어)
- 조합 최적화 문제 (Knapsack 변형 등)
- N이 많이 작은 경우 (백트래킹으로 푸는 문제일 거 같으면 가장 오래걸릴 TC를 직접 돌려보기)