[1분 요약] 백트래킹(Backtracking)이란?

백트래킹 이란?

해를 찾아가는 도중, 현재의 경로는 해가 될 수 없는 경우 그 경로를 더 이상 가지 않고 되돌아가는 기법을 말한다.

DFS 알고리즘에서, 절대 불가능한 경우에 대해  조건문을 걸어 탐색을 중지하고 되돌아가는 경우가 대표적인 예이다. 

 

불필요한 경로를 차단한다는 의미에서, '가지치기'라는 용어를 쓰기도 한다. 

때문에 찾아가야할 경우의 수를 줄일 수 있으므로, 백트래킹 기법을 이용해 시간 단축을 노려볼 수 있다.

 

 

* 핵심 표현

해가 될 가능성이 있는 경우, '유망하다(promising)' 라고 표현하고,

해가 될 가능성이 없는 경우에 그 경로를 가지 않게 하는 행위에 대해서는 '가지치기(pruning)'한다고 표현한다.