핵심 정리
text
선택한다
다음 상태로 내려간다
돌아오면서 선택을 취소한다
불가능한 가지는 더 내려가지 않는다| 요소 | 의미 |
|---|---|
| 상태 | 현재까지 고른 값 |
| 선택지 | 다음에 고를 수 있는 후보 |
| 종료 조건 | 답을 기록할 시점 |
| 가지치기 | 더 볼 필요 없는 상태 제거 |
구조
백트래킹은 DFS로 모든 가능성을 탐색하지만, 조건을 만족할 수 없는 가지는 중간에 멈춥니다. 순열, 조합, 부분집합, 퍼즐, 배치 문제에서 자주 사용합니다.
csharp
void Search()
{
if (path.Count == targetLength)
{
Save(path);
return;
}
for (int i = 0; i < n; i++)
{
if (used[i]) continue;
used[i] = true;
path.Add(items[i]);
Search();
path.RemoveAt(path.Count - 1);
used[i] = false;
}
}선택 후 재귀 호출, 호출 후 선택 취소가 백트래킹의 기본 모양입니다.
조합
조합은 순서가 중요하지 않으므로 다음 탐색 시작 위치를 넘겨 중복을 막습니다.
csharp
void Combine(int start)
{
if (path.Count == k)
{
Save(path);
return;
}
for (int i = start; i < n; i++)
{
path.Add(items[i]);
Combine(i + 1);
path.RemoveAt(path.Count - 1);
}
}가지치기
| 상황 | 가지치기 예시 |
|---|---|
| 현재 합이 이미 초과 | 더 내려가지 않음 |
| 남은 원소로 길이 부족 | 반복 중단 |
| 중복 값으로 같은 선택 반복 | 같은 깊이에서 중복 skip |
| 조건을 만족할 수 없음 | 즉시 return |
가지치기는 정답을 바꾸지 않으면서 탐색량을 줄여야 합니다. 조건을 너무 강하게 걸면 답을 버릴 수 있고, 너무 약하면 시간 초과가 납니다.
주의할 점
백트래킹은 최악의 경우 여전히 지수 시간입니다. n이 큰 문제에서 모든 순열이나 부분집합을 만들면 통과할 수 없습니다.
또 선택 취소를 빠뜨리면 다음 가지가 이전 상태를 물고 들어갑니다. Add와 Remove, used = true와 used = false가 짝을 이루는지 확인하세요.
참고 링크
1 sources