[알고리즘]백트래킹

백트래킹 이란
해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되달아 가는 방식이다.
즉 , 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것
답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하지 않는것

문제풀이시 DFS등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 이러한 상황일 경우 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 하는 방법

유망성 판단 : 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 판단된 노드의 이전(Backtracking)으로 돌아가 다음 자식 노드로 간다.
해가될 가능성이 있으면 유망하다고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기 라 한다.

출처 : https://chanhuiseok.github.io/posts/algo-23/

그래서 우리는 이 알고리즘을 언제 사용하냐 ? 모든 경우의수를 확인해야 하는데 for 로는 확인 불가한 경우 사용한다.(깊이가 달라질때)

시간복잡도
n^n	중복이 가능할때
n!	중복이 불가할때

✨Tip 백트래킹 문제는 n이 작다.