백트래킹(Back Tracking)

백트래킹

• 답을 찾는 도중에 답이 아니어서 막히면, 되돌아가서 다시 답을 찾아가는 방법을 말한다.
• 최적화 문제 와 결정 문제를 푸는 방법중 하나.

DFS와 비교

DFS

• DFS는 가능한 모든 경로를 탐색한다.(그 경로가 불필요하더라도)
• 그렇기에 경우의 수를 줄이지 못한다.

백트래킹

• 백트래킹은 지금 진행하고 있는 경로가 조건에 부합할 것 같지 않다면 거기서 되돌아간다.
• 이는 DFS와 다르게 반복의 횟수를 줄일 수 있기에 매우 효율적이다.
• 그러나 최악의 경우는 DFS와 동일한 탐색횟수를 갖게 된다. 그렇기에 얼마나 경로를 가지치기를 잘 해느냐가 관건
• 주로 탐색하는 과정에서 조건문을 걸어서 절대로 답이 될 수 없는 상황에 대해 미리 정의해두어서 탐색을 바로 중지할 수 있도록 한다.