백트래킹

백트래킹?

현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는, 즉 이름 그대로 방금 왔던 길을 되짚어가는, backtrack1 하는 알고리즘이다.

 

• Promising : 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크한다.
• Pruning (가지치기): 해당 트리에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지치기를 한다.

 

• 해를 구하는 도중 해가 아니어서 막히면 막히기 전으로 다시 돌아가서 해를 찾는 기법
• 가상의 트리에서 해를 구하기 위해 부모 노드에서 자식 노드까지 뻗어나간다. 만약 해당 노드가 조건에 맞지 않는다면 다시 부모노드로 돌아간다.
• 해가 아닌 선택지는 없애면서 탐색하기 때문에 시간복잡도를 줄일 수 있다.
• 불필요한 탐색을 하지 않는다.
•