Quick Flow
선택한다
다음 상태로 내려간다
돌아오면서 선택을 취소한다
불가능한 가지는 더 내려가지 않는다| 요소 | 의미 |
|---|---|
| 상태 | 현재까지 고른 값 |
| 선택지 | 다음에 고를 수 있는 후보 |
| 종료 조건 | 답을 기록할 시점 |
| 가지치기 | 더 볼 필요 없는 상태 제거 |
순열은 used, 조합은 다음 시작 index, 부분집합은 선택·미선택 분기로 중복을 막습니다. 결과에 현재 경로를 보관할 때는 가변 목록 자체가 아니라 복사본을 저장합니다.
구조
백트래킹은 DFS로 모든 가능성을 탐색하지만, 조건을 만족할 수 없는 가지는 중간에 멈춥니다. 순열, 조합, 부분집합, 퍼즐, 배치 문제에서 자주 사용합니다.
static List<int[]> Permutations(IReadOnlyList<int> values)
{
var result = new List<int[]>();
var path = new List<int>();
var used = new bool[values.Count];
void Search()
{
if (path.Count == values.Count)
{
result.Add(path.ToArray());
return;
}
for (int i = 0; i < values.Count; i++)
{
if (used[i]) continue;
used[i] = true;
path.Add(values[i]);
Search();
path.RemoveAt(path.Count - 1);
used[i] = false;
}
}
Search();
return result;
}선택 후 재귀 호출, 호출 후 선택 취소가 백트래킹의 기본 모양입니다. 위 함수는 값이 서로 다르다는 전제에서 순열을 만듭니다. 중복 값이 있으면 같은 값 순열도 중복 생성되므로, 정렬한 뒤 같은 깊이에서 같은 값을 건너뛰는 규칙을 추가해야 합니다.
조합
조합은 순서가 중요하지 않으므로 다음 탐색 시작 위치를 넘겨 중복을 막습니다.
static List<int[]> Combinations(IReadOnlyList<int> values, int count)
{
if (count < 0 || count > values.Count)
{
throw new ArgumentOutOfRangeException(nameof(count));
}
var result = new List<int[]>();
var path = new List<int>();
void Search(int start)
{
if (path.Count == count)
{
result.Add(path.ToArray());
return;
}
int remaining = count - path.Count;
for (int i = start; i <= values.Count - remaining; i++)
{
path.Add(values[i]);
Search(i + 1);
path.RemoveAt(path.Count - 1);
}
}
Search(0);
return result;
}부분집합
부분집합은 각 원소를 고를지 말지를 한 번씩 결정합니다. n개 원소라면 빈 집합을 포함해 2^n개 결과가 나옵니다.
static List<int[]> Subsets(IReadOnlyList<int> values)
{
var result = new List<int[]>();
var path = new List<int>();
void Search(int index)
{
if (index == values.Count)
{
result.Add(path.ToArray());
return;
}
Search(index + 1); // values[index]를 고르지 않음
path.Add(values[index]);
Search(index + 1); // values[index]를 고름
path.RemoveAt(path.Count - 1);
}
Search(0);
return result;
}입력 값이 중복되면 이 함수도 같은 값의 부분집합을 여러 번 만들 수 있습니다. 값 기준으로 중복을 제거해야 하면 입력을 정렬하고, 같은 재귀 깊이에서 같은 값을 건너뛰는 규칙을 추가합니다.
가지치기
| 상황 | 가지치기 예시 |
|---|---|
| 현재 합이 이미 초과 | 더 내려가지 않음 |
| 남은 원소로 길이 부족 | 반복 중단 |
| 중복 값으로 같은 선택 반복 | 같은 깊이에서 중복 skip |
| 조건을 만족할 수 없음 | 즉시 return |
가지치기는 정답을 바꾸지 않으면서 탐색량을 줄여야 합니다. 조건을 너무 강하게 걸면 답을 버릴 수 있고, 너무 약하면 시간 초과가 납니다.
주의할 점
백트래킹은 최악의 경우 여전히 지수 시간입니다. n이 큰 문제에서 모든 순열이나 부분집합을 만들면 통과할 수 없습니다.
또 선택 취소를 빠뜨리면 다음 가지가 이전 상태를 물고 들어갑니다. Add와 Remove, used = true와 used = false가 짝을 이루는지 확인하세요.
참고 링크
1 sources