Backtracking은 제약조건 만족문제에서 해를 찾는 방법이다.
개념 : 여러가지 경우의 수가 있는 문제에서 특정조건을 만족하는 찾는 데 있어, 조건을 탐색하다가 어느 순간 조건이 맞지 않는 것으로 판단되면 그 쪽의 경우의 수는 더이상 체크하지 않고 다른 경우의 수를 체크하는 것.
- 일종의 문제 푸는 전략으로, 알고리즘은 아니다.
- 고려할 수 있는 경우의 수를 상태공간트리로 표현
- DFS 방식으로 후보군 확인
- 상태공간트리 탐색하며 제약조건을 만족하지 않으면 해당 부분에서 파생될 수 있는 모든 경우의 수를 더이상 보지 않는다.
- 이후 해의 후보가 될 만한 곳을 바로 넘어가서 탐색을 이어간다.
- 이를 통해 체크해야 하는 조건의 수를 확연히 줄이므로 계산량을 줄일 수 있는 기법이다.
- Promising : 조건 검사 기법
- Prunning : 가지치기. 조건에 맞지 않으면 그 부분의 탐색은 포기하고 다른 루트로 돌아서서 탐색 시간 절약
< 정리 >
Backtracking은
트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건이 부합하는지 체크(Promising),
만약 해당 트리에서 조건에 맞지 않는 노드는 더이상 DFS 탐색 진행하지 않고 가지를 쳐냄(Prunning)