백트래킹(BackTraking)

백트래킹(BackTraking) 기법은 해를 찾는 도중에 '막히면' (즉, 해가 아니면) 되돌아가서 다시 해를 찾아 가는 기법이다.

이를 가지치기(Prunning)이라고도 하며, 이러한 가지치기를 통해 최적화 (Optimization) 문제와 결정 (decision) 문제를 해결할 수 있다.

※결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no'가 답하는 문제

가지치기(Prunning)

특정한 조건을 만족하는 경우만을 남기는 것.

DFS 등 모든 경우의 수를 탐색하는 과정 도중에 답이 될 만한지를 조건에 따라 판단하고 그렇지 않으면 해당 탐색을 중단하고 다음 탐색으로 넘어감