[Algorithm] Backtracking이란?

이번 시간에는 Backtracking에 대해서 알아봅시다!

 

Backtracking이란

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

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

 

DFS와 Backtracking

DFS

DFS는 가능한 모든 경로(후보)를 탐색합니다.

따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못합니다.

따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능할 것입니다.

---

Backtracking

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아갑니다.

즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.

이를 pruning(가지치기)라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다.

일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 

만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 exponential의 시간을 필요로 하므로 처리가 불가능할 수도 있습니다. Pruning을 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.

---

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

---

Backtracking 기법의 유망성(promising) 판단

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

 

해가 될 가능성이 있으면 유망(promising)하다고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning) 한다고 하는 것입니다.