[알고리즘] 백트래킹 (Backtracking)

백트래킹(Backtracking)이란 ?

해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말합니다.

최적화 문제와 결정 문제를 푸는 방법이 됩니다.

깊이 우선 탐색 (DFS) vs. 백트래킹 (Backtracking)

DFS

DFS는 가능한 모든 경로를 탐색합니다.
그러므로 불필요한 경로를 사전에 차단하는 등의 행동이 없으므로 경우의 수를 줄일 수 없습니다.
따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능합니다.

백트래킹

해를 찾아가는 도중 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더 이상 가지 않고 되돌아갑니다.
이를 가지치기라고 하는데 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다.
하지만 만약 N! 의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능할 수 있습니다.
그러므로 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.

백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것입니다.
답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하지 않고 가지치기하는 것입니다.
주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있습니다.

백트래킹 기법의 유망성 판단

어떤 노드의 유망성, 즉 해가 될만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 갑니다.

해가 될 가능성이 있으면 유망하다고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기라고 합니다.

 

 

---

참고

https://chanhuiseok.github.io/posts/algo-23/