알고리즘 정리 - 백트래킹(Backtracking)

정의

백트래킹 : 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시후보를 포기(백트랙, Backtrack)해 정답을 찾아가는 알고리즘

DFS는 백트래킹의 한 예

백트래킹은 주로 재귀로 표현됨.

최악의 경우 모든 경우를 다 거친 다음에 목적지에 도착하므로 부르트 포스와 유사함
하지만, 매번 같은 경로를 반복하는 부르트 포스보다 훨씬 좋은 방법
Why? => 가능성이 없는 경우 즉시 후보를 포기하기 때문!

"가지치기"라고도 불리움.
트리 탐색 최적화 문제와도 관련 있음

어디서 사용되나?

제약 충족 문제 (CSP, Constraint Satisfaction Problems) 풀이할 때 필수적임
Ex) 스도쿠, 십자말 풀이, 8 Queen, 4색 문제 같은 퍼즐 문제 등

출처 : 파이썬 알고리즘 인터뷰