[알고리즘] Back Tracking

백트래킹

완전탐색(Brute Force)에 조건에 맞지 않는 경로를 만나면 해당 경로가 아닌 다른 경로를 탐색하는 알고리즘이며 탐색해야하는 그래프가 트리일 때 주로 활용한다.

• 완전탐색 기반이기 때문에 DFS, BFS, Best First Search (최선 우선 탐색) 가능

⚠️ 일반적으로 DFS를 활용하지만 사이클이 있는 경우에 DFS는 무한재귀 위험

트리 구조일 때 활용이 적합하지만 트리 탐색 알고리즘보다는 효율적인 탐색 방식에 가깝기 때문에 백트래킹을 활용해도 괜찮은 그래프인지 확인하고 사용하자.

DFS | 종료(return) 조건을 잘 설정해서 백트래킹으로 효율 개선 가능
BFS | 분기점에서 조건에 맞지 않는 경로는 제외하고 탐색
Best First Search | 우선순위큐를 활용하여 BFS에서 최적의 경로가 될 수 있는 경로 우선 탐색

ex. 주어진 그래프에서 경로에 있는 노드의 합이 12 이하인 모든 경로를 탐색하는 문제 (Best First Search에서는 12가 작은 수이므로 작은 노드부터 계산하는 게 최선이라고 가정)

vs 그리디

그리디는 순간순간에 최선의 선택을 함
⇒ 결과적으로 최적일 수 있는 하나의 경로를 도출

백트래킹은 모든 경로를 탐색하는데 탐색 과정에서 조건에 안 맞으면 포기하는 방식
⇒ 결과적으로 조건에 맞는 (최적인) 경로를 도출