1. 백트래킹 (Backtracking) 정의
•
임의의 집합에서, 주어진 기준(criterion)대로 원소의 순서를 선택하는 문제를 해결하는 알고리즘 설계 방법.
•
대표적 사례: n-Queens 문제, 부분집합의 합 문제(sum of subsets problem).
•
해답 후보 공간을 트리 구조(상태공간트리)로 모델링하고, 가지치기(pruning)를 통해 불필요한 경로를 제거.
2. 상태공간트리와 깊이우선검색(DFS)
•
상태공간트리(state space tree):
모든 가능한 상태(해답 후보)를 트리로 표현.
뿌리에서 잎 노드까지의 경로가 해답 후보를 나타냄.
•
DFS:
뿌리 노드에서 시작하여 가능한 한 깊게 내려간 뒤, 더 이상 진행할 수 없으면 이전 노드로 돌아가 탐색을 계속.
3. 백트래킹의 핵심 논리
•
유망성(promising):
현재 노드가 해답의 일부가 될 가능성이 있으면 유망(promising), 그렇지 않으면 비유망(non-promising).
•
가지치기(pruning):
비유망한 노드에서 즉시 탐색을 중단하고 부모로 돌아감.
해답 가능성이 없는 부분공간을 검색하지 않음.
4. n-Queens 문제
4.1 문제정의
•
n × n 체스판에 n개의 여왕말(Queen)을 서로 잡아먹히지 않도록 배치.
•
한 행에 하나씩 Queen을 두면서,
같은 열/대각선에 있는지 검사(유망성 판단).
4.2 백트래킹 알고리즘(알고리즘 5.1)
•
각 깊이(depth) i에서 i번째 행에 Queen을 둘 column을 선택.
•
col[i] = i번째 행에 Queen이 위치한 column 값.
void queens(index i) { // i: 현재 행 번호
if(promising(i)) {
if (i==n) {
// 해답 col[1] ~ col[n] 출력
}
else {
for (j=1; j<=n; j++) {
col[i+1] = j;
queens(i+1);
}
}
}
}
bool promising(index i) {
for (k=1; k<i; k++) {
if(col[i] == col[k] || abs(col[i] - col[k]) == i - k)
return false;
}
return true;
}
C++
복사
•
promising: 같은 열, 대각선에 있는지 검사.
5. n-Queens 백트래킹 시간복잡도 분석
•
상태공간트리의 전체 노드 수는 nⁿ(모든 행에 대해 모든 열 시도)이나,
가지치기를 통해 탐색 노드 수가 대폭 감소.
•
같은 열에 Queen을 둘 수 없으므로, 유망 노드의 상한은 n!개.
•
실제 탐색 노드 수는 대각선 조건까지 포함하면 더 작아짐.
•
시간복잡도는 최악 O(n!)보다 작으나, 정확한 분석은 불가능(실행을 통한 경험적 추정 필요).
•
몬테카를로 방법 등 확률적 추정 기법으로 복잡도 추정 가능.
6. 부분집합의 합 문제 (Sum of Subsets Problem)
6.1 문제정의
•
n개의 아이템 무게 w₁, ..., wₙ과 목표 무게 W가 주어질 때,
무게의 합이 W가 되는 부분집합을 구하는 문제.
6.2 상태공간트리 및 가지치기
•
각 깊이에서 아이템 포함/불포함 두 갈래로 분기(2진 트리).
•
무게 합이 초과하면 그 경로는 가지치기(pruning).
6.3 백트래킹 알고리즘(알고리즘 5.4)
void sum_of_subsets(index i, int weight, int total) {
if (promising(i)) {
if (weight == W) {
// 해답 출력
} else {
include[i+1]=1;
sum_of_subsets(i+1, weight + w[i+1], total - w[i+1]);
include[i+1]=0;
sum_of_subsets(i+1, weight, total - w[i+1]);
}
}
}
bool promising(index i) {
return (weight + total >= W) && (weight == W || weight + w[i+1] <= W);
}
C++
복사
•
promising 조건:
(1) 남은 아이템을 모두 더해도 W 미만이면 가지치기
(2) weight + w[i+1]이 W를 넘으면(초과 시) 가지치기
7. 부분집합의 합 문제 시간복잡도
•
상태공간트리의 최대 노드 수: 2ⁿ⁺¹ – 1 = O(2ⁿ)
•
백트래킹/가지치기를 통해 많은 노드 생략 가능
•
최악의 경우 여전히 지수 복잡도,
평균적으로는 훨씬 적은 노드만 검사하게 됨
8. 몬테카를로 방법(Monte Carlo Algorithm)에 의한 복잡도 추정
•
표본 추출과 확률적 실험을 이용하여 실제 방문 노드 수의 기대값을 추정
•
n-Queens 등 백트래킹 적용 문제에서 평균 탐색량을 수치적으로 추정 가능
BackTracking#2
1. 지도색칠하기와 그래프 색칠하기
1.1 지도색칠하기 문제
•
인접한 지역(국가, 도, 구 등)이 서로 다른 색이 되도록 색을 칠하는 문제.
•
4색 정리(Four color theorem): 임의의 평면지도는 최대 4가지 색만으로 인접 지역을 모두 구분할 수 있다.
1.2 그래프 색칠하기 문제
•
각 지역을 그래프의 정점(vertex)으로, 인접 지역은 간선(edge)로 표현.
•
평면그래프(planar graph): 간선이 서로 교차하지 않고 평면상에 그려지는 그래프. 모든 지도는 평면그래프로 표현 가능.
•
비평면 그래프는 4색 정리를 적용할 수 없다.
1.3 m-색칠하기(m-coloring) 문제
•
최대 m가지 색을 사용하여 인접한 정점에 같은 색이 할당되지 않도록 그래프를 색칠.
•
인접행렬 W[i][j]=1이면 i, j 정점이 연결되어 있음.
•
백트래킹으로 해결 가능: 각 정점에 색을 할당하며 유망성을 검사(인접 정점과 색이 다르면 유망).
m-색칠하기 백트래킹 알고리즘 (알고리즘 5.5)
void m_coloring(index i) {
if(promising(i)) {
if(i==n) 출력;
else {
for(color=1; color<=m; color++) {
vcolor[i+1] = color;
m_coloring(i+1);
}
}
}
}
bool promising(index i) {
for(j=1; j<i; j++)
if(W[i][j] && vcolor[i]==vcolor[j]) return false;
return true;
}
C++
복사
•
상태공간트리에서 가지치기를 수행하여 불필요한 색 조합을 제외한다.
•
최악의 경우 상태공간트리의 노드 수는 mⁿ.
2. 0–1 배낭채우기 문제의 백트래킹
2.1 상태공간트리 구축
•
각 아이템을 포함/불포함으로 분기하는 2진 트리를 사용.
•
각 노드에서 누적 가치(profit), 누적 무게(weight)를 관리.
•
모든 해답 후보 경로를 따라 최적해(best)를 갱신해야 하므로, 최적화 문제로 분류된다.
2.2 유망성 판단과 가지치기
•
유망성(promising): 해당 노드의 bound(이론상 가능한 최대 이익)가 현재까지 찾은 최적 이익(maxprofit)보다 크면 유망.
•
bound 계산: 남은 용량이 있으면, 다음 아이템을 분할해서(무게당 가치로) 더해 최대로 만들 수 있는 이익의 상한선을 계산.
백트래킹 알고리즘 (알고리즘 5.7)
void knapsack(index i, int profit, int weight) {
if(weight <= W && profit > maxprofit){
maxprofit = profit;
bestset = include;
}
if(promising(i)) {
include[i+1]=1;
knapsack(i+1, profit+p[i+1], weight+w[i+1]);
include[i+1]=0;
knapsack(i+1, profit, weight);
}
}
bool promising(index i) {
int totweight = weight, j = i+1;
float bound = profit;
while(j <= n && totweight + w[j] <= W) {
totweight += w[j];
bound += p[j];
j++;
}
if(j <= n) bound += (W - totweight) * p[j] / w[j];
return (weight < W) && (bound > maxprofit);
}
C++
복사
•
profit: 현재까지 담은 아이템 가치 합
•
weight: 현재까지 담은 아이템 무게 합
•
bound: 추가로 얻을 수 있는 최대 이익의 상한
3. 시간복잡도
•
m-색칠하기 문제의 최악 시간복잡도: O(mⁿ) (m: 색의 개수, n: 정점 개수)
•
0–1 배낭문제의 백트래킹 알고리즘: 상태공간트리의 최대 노드수는 O(2ⁿ), 하지만 가지치기를 통해 실제 탐색량 감소.
•
최악의 경우에도 지수 복잡도(2ⁿ+1–1)이나, 실제로는 pruning으로 탐색 노드가 줄어듦.
4. 정리
•
백트래킹은 상태공간트리의 DFS와 가지치기를 결합한 해 공간 탐색 기법.
•
유망성 검사를 통해 비효율적인 탐색을 방지하고, 최적화/조합문제에서 효과적으로 사용됨.
•
대표적 예시: 그래프 색칠(m-coloring), 0–1 배낭문제, 부분집합의 합 등.
