[Algorithm] 백트래킹

기본 과정

1. DFS 진행
2. 방문 지점의 유망성(Promising) 확인

• 유망함(Promising) ??
  • 방문 중인 노드의 하위 노드에 해답이 존재할 가능성이 있는 상태
  • 반대 개념 유망하지 않음 ( non-promising)

3. 유망하지 않다면, 부모 노드(vertax)로 복귀
4. 스택의 활용
5. 현재 노드에서 하위 노드로 가도 해답이 없는 경우 == non-promising
6. 더 이상 하위 노드 (자식 노드)로 방문하지 않고, 부모 노드로 되돌아 간다.(backtracking)

• 기본 과정 - Backtracking & Prunning
  1. DFS로 탐색
  2. 방문 중인 노드의 유망성 검사
  3. 유망하지 않다면 부모 노드로 되돌아감(backtrack) == 가지치기 (Prunning)
  • 유망하지 않으면 하위 노드를 가지치기
  • 가지치기한 상태는 방문한 노드의 방문하지 않는 하위 트리(Pruned State)

# 노드 검사
def checknode (v) :
    # 유망함
    if promising(v) :
        # 해를 찾았다면
        if there is a solution at v :
            write the solution
        # 해가 아니라면
        else :
            # 해당 노드에서 계속 탐색
            for u in each child of v :
                checknode(u)
    # 유망하지 않음
    else:
        # 해당 노드에서 작업을 멈춤.
        # 즉, call stack의 최상위 함수를 실행시켜 마치 부모노드로 돌아가는 효과
        pass