[알고리즘] 되추적(Backtracking) - Part 1 상태 공간 트리

* 상태 공간 트리(State Space Tree)
 - 미로 찾기에서 입구에서 출구까지 가는 경로를 찾기 위해서 선택할 수 있는 모든 경로를 트리로 만들 수 있다.
   막다른 곳이나 출구가 종단 노드(leaf node)에 위치하게 된다. 이 트리가 상태공간 트리이다.
 - 상태 공간 트리를 깊이 우선 검색을 하여 해답 후보들 중에서 해답을 찾을 수 있다.
  > 상태 공간 트리를 깊이 우선 검색을 하여 해답 후보들을 모두 순회하면서 해답을 찾을 수 있다.
     그러나 이방법은 해답이 될 가능성이 전혀 없는 노드의 후손 노드들도 모두 검색해야 하므로 비효율 적이다.

* 되추적 기술
 - 노드의 유망성
  > 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않다고 판단을 한다.(non-promising)
     이와 반대로 가능성이 있는 노드를 유망하다고 판단한다.(promising)
 - 되추적이란?
  > 어떤 노드의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 노드의 부모 노드로 돌아가서(backtracks)
     다음 자식 노드에 대한 검색을 계속하는 것이다.
  > 되추적 알고리즘의 개념
   + 되추적 알고리즘은 상태공간트리에서 깊이 우선 검색을 실시하면서, 유망하지 않는 노드들의 가지를 치면서
     (pruning) 검색을 계속하지 않는다. 반대로 유망한 노드에 대해서는 계속해서 검색을 실시한다.

* 되추적 알고리즘
 1. 상태 공간 트리에 대해 깊이 우선 검색을 실시한다.
 2. 각 노드가 유망한지를 점검한다.
 3. 만약, 그 노드가 유망하면 그 노드의 자식 노드들에 대한 검색을 계속한다. 그렇지 않으면 그 노드의 부모
    노드로 돌아가서 검색을 계속한다. 

 void checknode(node v){

   if ( promising(v) ) 
     if ( there is a solution at v ) write the solution
     else
       for ( each child u of v ) checknode(v);
 }