백트래킹(Back-Tracking)

🔹 DFS(Depth-First Search)

• 깊이 우선 탐색 DFS는 가능한 모든 경로(후보)를 탐색한다. 따라서, 불필요할 것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 최적으로 줄이지 못한다.
• 따라서, N! 의 경우의 수를 가지는 문제는 DFS로 처리하지 못할 가능성이 매우 크다.

 

🔹 백트래킹(Back-Tracking) ?

• 해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아가는 기법
• 해를 찾아가는 도중에 지금의 경로가 해가 될 것 같지 않다면, 더 이상 깊이 들어가지 않고 이전 단계로 돌아간다.
• 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 방향으로 나아가는 방식이기 때문에 경우의 수가 줄어들지만,
• 만약 N! 의 경우의 수를 가진 문제에서는 최악의 경우 여전히 DFS(Depth-First Search)와 같은 시간을 필요로 하므로 처리가 불가능할 수도 있고 가능할 수도 있다.
• 그렇기 때문에, 가지치기를 얼마나 잘하느냐에 따라서 효율성이 결정된다.

 

🔹 알아두면 좋은 백트래킹 용어

• Promising : 해가 될 가능성이 있는 유망(promising) 한 상태
• Pruning : 해가 될 가능성이 없는 경우, 해당 노드를 제외하는 행위
• Backtracking : 유망하지 않은 방향으로 더 이상 진행하지 않고 되돌아(backtracking) 오는 행위

 

🔹 백트래킹의 유망성 판단

• 어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후에 유망하지 않다고 결정되면, 그 노드의 이전 노드(부모)로 돌아가 (backtracking) 다음 자식 노드로 이동한다.
• 해가 될 만한 가능성이 있다면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning)라고 한다.

 

🔹 언제 사용하면 좋을까 ?

• 일정한 크기의 조건들이 주어지고, 그 안에서 완전 탐색을 통해 최적 비용 또는 최적 경로를 탐색해야 하는 경우
• 각 조건에서 선택할 수 있는 경우의 수가 정해져 있을 경우

 

 

 

 

 

📃 reference

• https://chanhuiseok.github.io/posts/algo-23
• https://gukin.tistory.com/34
• https://wikidocs.net/124273