[알고리즘] Backtracking ( 백트래킹, 퇴각 검색 )

• Backtracking에 대한 정의
• DFS와 비교 

---

백트래킹은 '조합 알고리즘 문제'에 대해 모든 가능한 해를 나열하는 것이다.

모든 조합의 수를 살펴보는 것인데 단 조건이 만족하는 경우에만 해당된다.

출처 : https://www.programiz.com/dsa/backtracking-algorithm

즉 주어진 조합을 탐색 시 답이 될만한지 판단하고 그렇지 않으면 해당 조건은 탐색을 멈추고 가지치기를 하는 것이다.

완전 탐색에서 좀 더 효율적으로 유망성을 판단하고 가지치기를 수행한다.

 

완전 탐색 : 여러 개의 solution을 가진 문제에서, 모든 solution을 탐색하는 전략

DFS와 비교 

대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색)가 있다.

DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출 또는 Stack을 이용해서 계속 이동한다. 

하지만 DFS는 모든 노드를 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 탐색을 수행할 수도 있다.

 

백트래킹은 DFS에 가지치기 (Pruning)를 통해 불 필요한 탐색을 제한하는 완전 탐색 기법이다.

가지치기를 얼마나 잘하느냐에 따라서 효율이 극대화될 수 있는 방법이다.

 

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