[Algorithm] 순환 ⑥

<N-Queens 문제> : 가로 크기가 N , 세로 크기가 N인 2차원 체스 보드에서 N개의 말을 동일한 열, 행, 대각선에

                           두지 않도록 만드는 것 => Backtracking(내가 했던 결정을 번복하고 다른 선택) 방법 사용 가능 

 

- 상태공간트리 : 찾는 해를 포함하는 트리. 즉, 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당하며

                      이 트리를 체계적으로 탐색한다면 해를 구할 수 있음을 의미함. 하지만 상태공간 트리의 모든

                      노드를 탐색해야 하는 것은 아님. 아래의 노드를 더 이상 탐색할 필요가 없음을 infeasible하다고 표현.

 

- 되추적 기법(Backtracking) : 상태공간 트리를 깊이 우선 방식으로 탐색(깊이우선탐색)하여 해를 찾는 알고리즘

                                      코드로 구현 할 때, recursion 또는 stack으로 구현할 수 있으나 대부분 recursion을 사용.

 

- Design Recursion        ↗ 매개변수는 내가 현재 트리의 어떤 노드에 있는지를 지정해야 함.

return-type queens ( arguments ) {

     if non-promising

         report failure and return ; // infeasible하여 아래의 노드를 탐색할 필요가 없는 꽝인 노드인가

     else if success

         report answer and return ; // 찾고 있던 노드라면 답을 출력하거나 return

     else

         visit children recursively ; // 노드가 꽝도 아니고 찾던 답도 아니라면 아래의 자식 노드를 탐색

}

 

- 단계1

: 매개변수를 전달해 주는 방법 ( 전역변수 cols / 매개변수 level )

 

int [ ] cols = new int [ N+1 ] ;

return-type queens ( int level )

{

     if non-promising

          report failure and return ;

     else if success

          report answer and return ;

     else

          visit children recursively ;

}

=> 매개변수 level은 현재 노드의 레벨을 표현하고, 1번에서 level번째 말이 어디 놓였는지는 전역변수인

     배열 cols로 표현함. cols[i] = j는 i번 말이 (i행, j열)에 놓였음을 의미함.

 

- 단계 2

 

int [ ] cols = new int [ N+1 ] ;

boolean queens ( int level )

  {

     if ( !promising ( level ) )

          return false ;

     else if ( level == N )

          return  true;

     for ( int i = 1 ; i <= N ; i ++ ) {

          cols [ level+1 ] = i ;

          if ( qeens ( level+1 ) )

               return true ;

  }

  return false ;

}

 

- 단계 3

Promising Test(마지막에 놓인 이 말이 이전에 놓인 다른 말들과 충돌하는지 검사하는 것으로 충분)는 어떻게 할 것인가

 

boolean promising ( int level )

  {

     for ( int i = 1 ;