백트래킹 (Backtracking)

• 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아감
• 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적
• 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 가는 것 (가지치기)
• 일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요하므로 처리가 불가능할 수 있음. 따라서 가지치기를 얼마나 잘하느냐에 따라 효율성 결정
• 즉 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것
• 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것
• 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현 가능
• 해가 될 만한지 판단 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 감
• 해가 될 가능성이 있으면 유망하다(promising), 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning)라고 함