[알고리즘] 7. 백트래킹 기법(Backtracking)

백트래킹 기법은 해를 찾는 도중, 해가 될 가능성이 없으면 이전으로 되돌아가면서 시간을 아끼는 방법이다.

 

보통 구현 방식은 DFS의 중간에 조건식을 넣어서, 더 깊게 들어가봤자 의미가 없다는 것을 판단시킨 후, 이전으로 돌아가게 하는 식으로 한다. 이 과정을 가지치기라고 하고, 이 가지치기의 조건을 얼마나 잘 설정하느냐가 관건이 된다.