[필수 알고리즘] 재귀호출 기본 -백트래킹(Backtracking)

백트래킹 알고리즘

백트래킹(Backtracking)

위 단어를 그대로 해석하고 이해하면 된다.좀더 알고리즘적으로 설명하자면, 어떤 노드의 '유망성'을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가 다른 자식 노드를 찾는 방법이다.

즉, 모든 경우의 수를 찾아보지만, 그 중에서도 가능성만 있는 경우의 수만 찾아보는 방법이다.

 

백트래킹, 그리고 DFS(깊이우선탐색)를 혼동하는 경우가 있어 이에 대해 정리를 한 번 하고 가는게 좋다.

 

예로들어 이러한 문제가 있다고 가정해보자. 

" a + b + c + d = 20 을 만족하는 두 수를 모두 찾아내시오. ( 0 ≤ a ,b ,c ,d < 100) "

 

백트래킹은 앞서 말했듯이 해당 노드의 유망성을 판단한다고 했다. 이 말은 즉 해당 범위 내에서 조건을 추가하여 값의 유망성을 판단한다는 의미이다. 하나라도 a = 21 또는 b = 21 또는 c = 21 또는 d = 21 일 경우 20일 가능성이 1 ~ 100 범위 내에서는 절대 불가능하다. 그렇기 때문에 a > 20 이거나 b > 20, c > 20, d > 20 일 경우는 탐색하지 않는다. 그렇게 된다면 탐색하는데 필요한 자원을 많이 줄일 수 있다.

 

DFS(깊이우선탐색)은 트리순회의 한 형태다. 하나의 순회 알고리즘으로 백트래킹에 사용하는 대표적인 탐색 알고리즘이다. 즉, 백트래킹 == DFS가 아니라 백트래킹의 방법 중 하나가 DFS인 것이다. 그 외에도 BFS(너비우선탐색) 등 다양한 방법으로 백트래킹을 구현할 수 있다. 

 

😎정리 

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

다음은 DFS, BFS 알고리즘에 대해서 포스팅 하도록 하겠습니다.