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이 되는 경우의 수를 찾아내는 문제
아래 문제에는 선택된 원소 출력을 위해 비트마스킹을 이용했지만, 백트래킹을 이해하는데 몰라도 상관없는 내용이다.
반응형