Backtracking

Backtracking
백트래킹
출제 빈도가 높다.
백트래킹 알고리즘은 모든 경우의 수를 고려해야 할 때, 일반적으로 첫 번째로 사용해 볼 수 있는 접근 방법 중 하나 이다.
일반적으로 그래프/트리의 모든 원소를 완전 탐색 하기 위한 목적으로 사용할 수 있다.
해가 아니라면 다시 돌아온다. → 가지 치기
해를 찾는 도중 해가 절대 될 수 없다고 판단되면 되돌아가서 해를 다시 찾아가는 기법을 말한다. (되추적)
불필요한 경로는 굳이 끝까지 탐색하지 않겠다는 것이다. 직관적으로 봐도 백트래킹의 효율성은 얼마나 가지 치기를 적절히 해낼 수 있는 지가 중요하다.
백트래킹은 모든 경우의 수에서 조건을 만족하는 경우를 탐색하는 것이기 때문에 완전 탐색 기법인 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)로 모두 구현이 가능하다.
백트래킹 특성에서 조건에 부합하지 않으면 이전 수행으로 돌아가야 함으로 BFS보다는 DFS이 구현하기 더 편하기 때문에 주로 DFS를 사용한다.

유망함 (promising)