[알고리즘] 되추적(Backtracking) - Basic 깊이 우선검색

* 되추적이란?
 - 미로에서 출구를 찾다보면 막다른 곳에 도달 할 수 있다. 이때 마지막 분기점으로 되돌아 가서 다른 길로 갈 수
   있다. 이처럼 되추적은, 어떤 집합에서 특정 기준을 만족하면서 그 집합에 속한 대상의 순서를 손택하는 문제를
   푸는데 사용한다. 되추적의 기본은 상태 공간 트리로 깊이 우선 검색과 밀접한 관련이 있다. 일단 깊이 우선
   검색을 먼저 알아보도록 하자.

* 깊이우선 검색
 - 한 그래프의 정점들을 방문하는 하나의 방법
 - 슈도코드
  void DFSEARCH(v){
    정점 v를 "방문함"으로 표시한다.
    v에 인접한 모든 정점 w에 대해서 다음을 수행한다.
     > w가 방문하지 않은 상태면 DFSEARCH(w)를 수행
     > w가 이미 방문했던 상태면 수행을 종료한다.
  }  // 처음 모든 정점들은 방문 안함으로 표시를 한다.
 
  ex)

   

  결과 : 

 

 선택되지 않은 연결선 즉, 결과에서 나타난 빨간색 선은 "뒤 연결선(back edge)"이라고 한다. 그리고 옆의 그림과 같이 그래프의 모든 정점이 연결되어 있다면, 모든 정점을 방문이 가능할 것이다. 즉, 트리 연결선들이 깊이 우선 신장 트리를 형성한다는 것이다.

 이와 대조적으로 그래프의 모든 정점이 연결되어 있지 않다면, 트리가 여러개의 형태로 나타나 이는 깊이 우선 신장 숲(Depth first spanning forest)를 형성한다.

 한 가지 추가적으로 이야기하면, 간선(v,w)가 뒤 연결선이라면 신장트리에서 v가 w의 선조이거나 w가 v의 선조이다. 위에서 (2,4)가 뒤 연결선인데, 2가 4의 선조임을 볼 수 있다.










* 깊이 우선 검색 알고리즘
 - 데이터
  > G(V,E) : 주어진 그래프
  > num(x) : 정점 x를 방문하는 순서
  > T : 트리 연결선들의 집합
  > B : 뒤 연결선들의 집합
  > i : 방문 순서
 - 알고리즘
 for all x ∈ V { num(x) = 0; } // 모든 정점을 방문 안함으로 표시를 한다.
 i = 0;
 T = B = null;
 for all v ∈ V { if(num(x) == 0) DFS(x,0);
 void DFS(v,u){ // u는 v의 부모
   i = i + 1;
   num(v) = i;
   for ( w ∈ Adj(v) ) { //Adj(v) : v에 인접한 정점들
     if ( num(w) == 0 ) { // 방문하지 않았으므로 이 연결선은 트리 연결선으로 추가한다.
       T = T ∪ {(v,w)};
       DFS(w,v);  // 새로 추가단 간선,노드에대해서 다시 검사를 해본다.
     }else{ 
       if ( num(w) < num(v) and w != v ){ // (v,w)는 뒤 연결선이다. 이미 한번 방문을 했다.
         B = B ∪ {(v,w)};
       }
     }
   }

 - 알고리즘 분석 : O(|V| + |E|)