되추적(Backtracking)

Backtracking

어떤 노드의 유망성 점검 후, 유망하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색

한정 조건을 가진 문제를 풀려는 전략

유망하지 않으면 stack 에서 배제 하고 부모노드로 돌아가므로 풀이 시간이 단축됨

stack 에 자손을 넣기 전에 먼저 검증하므로 단순 DFS (깊이 우선 탐색) 보다 속도가 빠름