백트래킹

기본적으로 모든 경우를 탐색하며, DFS/BFS와 방식은 유사하다.

하지만 백트래킹은 가지치기를 통해 탐색 경우의 수를 줄인다는 차이가 있다.

정리하면,

• 백트래킹은 최악의 경우에는 모든 경우를 다 살펴보게 될 수도 있지만, 가지치기를 통해서 가능한 덜 보겠다는 전략이다.
• 가지치기의 원리는 가망성이 없으면 가지 않겠다는 원리를 바탕으로 한다.
• 어려운 문제일수록 극한의 가지치기를 요구할 수 있음