<aside> 💡 백트래킹(Backtracking): DFS와 같은 방식으로 탐색하는 모든 방법. 탐색을 하다 더이상 진행할 수 없으면 왔던 길을 되돌아가 다른 길을 찾는 방법

</aside>

DFS

• DFS는 가능한 모든 경로를 탐색합니다. 따라서, 불필요한 경로도 모두 탐색함으로써 경우의 수를 줄이지 못하고 연산하게 된다.

Backtracking

• 기본적으로 탐색을 하다 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 탐색한다.
• 가지치기를 통해 탐색할 곳과 탐색하지 않을 곳을 결정하는데 가지치기의 효율이 알고리즘의 성능을 결정한다
• DFS 혹은 상태탐색트리 등으로 경우의 수를 탐색하는 과정에서 탐색하지 않는 경로는 조건을 걸어 이전으로 돌아가 다른 경로를 탐색하게 한다.