재귀 + 브루트포스 + "후보에서 탈락 시 해당 파트의 탐색 종료"
재귀 + 브루트포스가 DFS라면 (모든 조건을 다 탐색)
백트래킹은 모든 경우를 탐색하되 불가능한 후보임을 발견하면 해당 경우는 탐색을 종료한다.
시간 복잡도는 브루트포스와 동일하나 대부분의 경우에서 브루트포스보다 빠르게 동작한다.
후보에서 탈락
방문 중인 노드가 유망한지 체크하고,
유망하지 않다면 하위 트리를 가지치기한다.
종료 조건에 도달한 경우(마지막까지 유망한 경우의 수), 전역으로 선언된 결과값에 이를 반영한다.
구현
def check_node(node, target):
global answer # 정답을 담을 변수는 함수 밖에서 관리
if not promising(node): # 방문 중인 노드가 유망하지 않다면
return # 부모 노드로 되추적(backtracking)
if isAnswer(node, target): # 해당 노드가 해답에 해당하면
answer += node # 정답 값에 반영
return
for i in node: # node의 모든 자식 노드에 대하여
check_node(i) # 추적