Algorithm자료구조론

알고리즘 N-Queen 문제

, ,

1. N-Queen문제

2. 컴퓨팅적 스킬

  • Recursive() 재귀함수 어느지점에서 종료시키고, 다시 재귀호출을 해야하는지의개념을 확실하게 알고 있어야합니다.
  • Recursive()의 개념을 잡기에 좋은 문제는 백준 N과 M시리즈 입니다. 개념이 약하신분들은 순열과 조합의 개념부터 확실히 잡고 오시는것이 좋을 것이라고 생각을 합니다.
  • 백트래킹 깊이우선탐색(DFS)의 개념을 알아야합니다. 깊이우선탐색은 보통 Recursive, Stack를 사용합니다. Recursive가 직관적이고 코드이해하기도 쉽고, 스택보다는 구현이 덜 복잡하다는 장점이 있어서 Recursive로 구현하겠습니다.

3. 컴퓨팅적 사고

  • 깊이우선탐색(DFS) 진행한 Level과 모든 말을 놓는 경우의 수가 같을때 재귀호출을 종료해야합니다.

  • NNN … N^N의 시간복잡도를 갖습니다.

  • 백트래킹의 개념에 대해 알고 있어야 한다. 깊이우선탐색의 트리형태로 어떻게 진행하는지 직접 손으로 써보면서 진행해야합니다.

  • 상태공간트리의 개념을 알고 있어야합니다.

    • 상태공간트리란 찾는 해를 포함하는 트리이며 이트리안에 어떠한 노드에 해당하는 이 트리를 체계적으로 탐색하면서 반드시 해를 찾을 수 있어야합니다.

  • 해당 퀸이 열 있는지 체크와 대각선을 체크해야합니다.

예를 들어 설명하겠습니다.

1
2
3
4
5
start에서 시작하면서 트리의 형태로 가지를 치면서 진행합니다. start-> (0,0) (0,1) (0,2) (0,3)  첫번째 열에서 갈수 있는 모든 경우의 수입니다.

(1,0) (1,1) (1,2) .... 두번째 열에서 갈 수 있는 경우의 수

(level, 1) (level, 2) (level, 3) Level 크기에서 갈 수 있는 경우의 수
0 1 2 3
Level 0 (0,0) (0,1) (0,2) (0,3)
Level 1 (1,0) (1,1) (1,2) (1,3)
Level 2 (2,0) (2,1) (2,2) (2,3)
Level 3 (3,0) (3,1) (3,2) (3,3)

다음의 상황은 Level 0 ~ Level N 의 경우까지 진행하는 경우라고 생각하겠습니다.

  • Level0의 경우에서 갈 수 있는 모든경우를 탐색하면서 퀸을 놓습니다. 그리고 다음 Level1으로 진행하면서 열에 들어갈 수 있는 경우를 확인하면서 진행합니다. 이때 알아야 하는 부분이 Promissing의 개념입니다.

  • 즉,Level0 (0,0)에 퀸을 놓으면 Level1 (1,0)에 퀸을 놓는 경우를 확인해보겠습니다. 퀸을 놓을 수 있는 조건은 동, 서, 남, 북, 대각선에 퀸이 위치해있으면 놓을 수 없습니다. 그러면 당연히 (1,0)은 확인할 필요도 없이 놓을 수 없는 경우의 수라는것입니다. 이것을 Promissing의 개념을 확인하여 더 갈 수 있는지 없는지를 판단하는 것입니다. 체크한다고 하시면 됩니다.

  • 레벨의 수가 결국 말의 개수를 뜻합니다. 제 코드에서는 cols라는 배열이 쓰이는데 이것은 현재 말이 어디에 놓였는지에 대한 위치입니다. cols[1] : 1번말이 놓인 열 , cols[2] : 2번말이 놓인 열 … cols[i] = j (i번말이 j에 놓였다는 의미입니다. i는 결국 레벨입니다.)

  • Promissing Test를 진행할 때 마지막에 놓인 이 말이 이전에 놓인 다른 말들과 충돌하는지 검사를 하면 퀸을 놓을수 있는지 없는지를 확인 할 수 있습니다.

3.1. Recursive 설계

  1. promising()함수를 호출합니다. 진행이 가능한지 여부를 확인하고 아니면 false, 가능하면 true를 리턴합니다.
1
2
3
4
// 1. 정답을 찾을 수 없는 경우 예를 들어 1,1 에서 2,1은 당연히 될수없는것이니까 프로미싱을 확인한다고 생각하면 된다.
 if(!promissing(level,N)){
     return false;
 }
  1. Level과 N의 값이 같은 경우(성공한 경우)
1
2
3
4
5
// 성공적으로 도착하였을 경우
  else if(level == N){
      // 기존의 N-queen의 위치를 구하면 종료하는 형식이였지만, 모든 경우의 수를 구하기 위해서는 해당 cnt값을 증가시켜주어서 확인할 수 있다.
      cnt+=1;
  }
  1. Level과 N의 값이 같지 않은 경우 Recursive() 재귀 함수 호출
1
2
3
4
5
6
7
for(int i=1; i<=N; i++){
     cols[level+1] = i;
     // 다음 레벨로 재귀 호출
     if(recursive(level+1,N)){
         return true;
     }
 }

3.2. Promising Test 설계

  1. 같은 열을 확인하여야합니다.
1
2
3
4
// 같은 열에 놓였는지 확인 (레벨과 행이 같다는 의미임(결국 충돌이 있다는 의미))
      if(cols[i] == cols[level]){
          return false;
      }
  1. 같은 대각선에 놓였는지를 확인하여야 합니다.
1
2
3
4
// 대각선에 충돌되는것 확인
    else if((level-i) == abs(cols[level] - cols[i])){
        return false;
    }

4. 풀이

4.1. 1. DFS 백트래킹 해당 값 찾기(기본 개념)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//
//  n-queen.cpp
//  algorithm-level-up
//
//  Created by kgh on 22/11/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;
int cols[10001];
int cnt = 0;
bool promissing(int level,int N){
    for(int i=1; i<level; i++){
        // 같은 열에 놓였는지 확인 (레벨과 행이 같다는 의미임(결국 충돌이 있다는 의미))
        if(cols[i] == cols[level]){
            return false;
        }
        // 대각선에 충돌되는것 확인
        else if((level-i) == abs(cols[level] - cols[i])){
            return false;
        }
    }
    return true;
}
bool recursive(int level,int N){
    // 1. 정답을 찾을 수 없는 경우 예를 들어 1,1 에서 2,1은 당연히 될수없는것이니까 프로미싱을 확인한다고 생각하면 된다.
    if(!promissing(level,N)){
        return false;
    }
    // 성공적으로 도착하였을 경우
    else if(level == N){
        for(int i=1; i<=N; i++){
            cout << "(" << i << "," << cols[i] << ")";
        }
        return true;
    }
    for(int i=1; i<=N; i++){
        cols[level+1] = i;
        
        // 성공할 경우
        if(recursive(level+1,N)){
            return true;
        }
    }
    return false;
}
int main(void){
    int N = 8;
    recursive(0,N);
    cout << cnt;
    return 0;
}


4.2. 2. DFS 백트래킹 해당 값 찾기(경우의 수 찾기 백준 문제)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//
//  n-queen.cpp
//  algorithm-level-up
//
//  Created by kgh on 22/11/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;
int cols[10001];
int cnt = 0;
bool promissing(int level,int N){
    for(int i=1; i<level; i++){
        // 같은 열에 놓였는지 확인 (레벨과 행이 같다는 의미임(결국 충돌이 있다는 의미))
        if(cols[i] == cols[level]){
            return false;
        }
        // 대각선에 충돌되는것 확인
        else if((level-i) == abs(cols[level] - cols[i])){
            return false;
        }
    }
    
    return true;
}
bool recursive(int level,int N){
    // 1. 정답을 찾을 수 없는 경우 예를 들어 1,1 에서 2,1은 당연히 될수없는것이니까 프로미싱을 확인한다고 생각하면 된다.
    if(!promissing(level,N)){
        return false;
    }
    // 성공적으로 도착하였을 경우
    else if(level == N){
        // 기존의 N-queen의 위치를 구하면 종료하는 형식이였지만, 모든 경우의 수를 구하기 위해서는 해당 cnt값을 증가시켜주어서 확인할 수 있다.
        cnt+=1;
    }
    for(int i=1; i<=N; i++){
        cols[level+1] = i;
        
        // 성공할 경우
        if(recursive(level+1,N)){
            
            return true;
        }
    }
    return false;
}
int main(void){
    int N;
    cin >> N;
    recursive(0,N);
    cout << cnt;
    
    return 0;
}
Share