[ALGORITHM] 백트래킹

백트래킹 (Backtracking)

• 제약 조건 만족 문제에서 해를 찾기 위한 전략
• 해를 찾기 위하여, 후보군 제약조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 Backtrack(다시는 해당 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가, 최적의 해를 찾는 방법
• 실제 구현시, 고려할 수 있는 모둔 경우의 수를 상태공간트리(State Space Tree)를 통하여 표현
• 각 후보군은 DFS로 확인하며, 상태공간 트리를 탐색하면서, 제약이 맞지 않으면 후보가 될만한 곳으로 넘어가서 바로 탐색

---

상태공간트리 (State Space Tree)

출처 : https://iamharshit2309.medium.com/backtracking-algorithm-91ff147e0a8e

• 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리

---

상태공간트리 탐색 기법

• Promising : 해당 루트가 조건에 맞는지 검사하는 기법
• Pruning (가지치기) : 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법

---

백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하며, 각 루트에 대한 조건에 부합하는지 체크(Promising)하고, 만약 해당 트리에서 조건에 맞지 않는 노드는 더이상 DFS로 탐색을 진행하지 않고 가지치기(Pruning)함