[알고리즘] 백트래킹(Backtracking)

0. 백트래킹

Go as deep as possible, backtrack if impossible

 

모든 조합을 시도해서 문제의 해를 찾는 알고리즘이다.

모든 가능성을 하나의 트리(상태 공간 트리)처럼 구성할 수 있으며, 가지 중에 정답이 있다.

하지만 모든 경로를 찾는 것은 비효율적이기 때문에, 해답이 될 가능성이 있는 선택지만 타고 들어간다.

즉, 완전 탐색(순열, 조합, 부분집합, BFS, DFS 등) + 가지 치기라고 생각하면 편하다.

상태 공간 트리(State-Space Tree)
문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리
ex) 미로를 해결할 때 갈림길에 놓인 지점

가지치기(pruning)
가능성이 없는 노드가 포함되는 경로는 더 이상 고려하지 않는다.

---

1. 적용 예시

n-queen

n*n 체스 보드판에서 n개의 queen을 서로 공격하지 못하도록 배치하는 경우의 수를 찾아내는 문제

 

부분 집합의 합

n개의 자연수로 이루어진 집합이 있을 때, 집합의 원소를 모두 더한 값이 m이 되는 경우의 수를 찾아내는 문제

아래 문제에는 선택된 원소 출력을 위해 비트마스킹을 이용했지만, 백트래킹을 이해하는데 몰라도 상관없는 내용이다.