어떤 노드의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 노드의 후손 노드(서브 트리)들에 대한 검색을 중지하고, 그 노드의 부모노드(parent)로 돌아간다 ("backtrack").
DFS는 가능한 모든 경로(후보)를 탐색합니다. 즉, 불필요한 노드까지 모두 검색해야 하므로 비효율 적이다.
어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가 다음 자식 노드로 갑니다.
해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning) 한다고 하는 것입니다.