[알고리즘] 백트래킹(Backtracking)

- 백트래킹

• 여러 가지 선택지들이 존재하는 상황에서 한 가지 선택
• 선택하면 새로운 선택지들 집합이 생성됨
• 선택들을 반복하며 최종 상태에 도달

 

- 백트래킹과 완전탐색(DFS)의 차이

• 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다.(가지치기)
• 완전 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단한다.
• N! 가지의 경우의 수 같이 완전 탐색 하기 힘들 때 좋다.
• 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만 최악의 경우에는 지수함수 시간을 요하므로 처리 불가능할 수 있다.