[Backtracking] 백트래킹 알고리즘의 정의

DFS(깊이 우선 탐색) 복습

DFS는 가능한 모든 경로(후보)를 탐색합니다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못합니다.

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

Backtracking 알고리즘이란 ?

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

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

 

깊이 우선 탐색에서는 한 루트를 끝까지 들여다보고 정답이 없을 시 처음으로 되돌아와서 다른 루트를 검사하는데, 이 과정에서 깊은 탐색에는 유용하지만 해당 루트에 답이 없을 시 많은 시간을 허비하게 됩니다.

그래서 시간을 단축시키기 위해 특정 루트에 들어가기 전에 이 루트가 유망한지(정답이 있을 확률이 높은지) 유망하지 않은지(정답이 있을 확률이 낮은지)를 판단하여 이 루트를 배제(검사를 하지 않음) 할지 말지 판단하는데, 이를 가지치기라고 합니다.

 

다시 말해 백트래킹 알고리즘은 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.

일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있습니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.

 

정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것입니다.

즉, 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것을 백트래킹이라고 생각하면 됩니다.

 

주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있습니다

 

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

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

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

 

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

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제