Easy is Perfect

[백준] 9663번 C/C++ 풀이 _ N-Queen

  • melonicedlatte
  • Feb 08, 2018


출처 : https://www.acmicpc.net/problem/9663

N-Queen 실패 풀이

시간 제한메모리 제한제출정답맞은 사람정답 비율
10 초128 MB61193363238955.740%

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 

8

예제 출력 

92

힌트

출처

이 문제는 어렵지 않다고 생각했는데, 시간이 상당히 많이 걸렸다. 
기본적으로 사용하는 알고리즘은 dfs 에다가 백트래킹을 적용하여 속도를 줄이는 기법이다. 

처음에 내가 생각한 풀이는 12 이상이 되면 급격하게 느려져서 결국 해답을 보고 풀이했다. 
기본 개념은 똑같았는데, 중간에 사용하는 계산법에서 속도가 차이가 좀 나서 그런 차이가 나는 것 같다. 

먼저 위에 그림처럼 첫 라인에 돌을 하나 놔둔다. 
그 다음에 바로 아래 줄을 for문을 통해서 조건탐색을 해준다. 


조건 체크를 해 주어야 할 부분은, 아래와 같이 나타나게 된다.
이 때, 나는 2중 배열을 사용해서 돌이 있는 영역을 표시해주고, for문을 사용해서 모든 칸을 하나하나 조사하는 방법을 사용했는데, 
다른 문제 풀이를 보니 규칙을 사용해서 훨씬 더 빠르게 했다. 

오른쪽이 위인 대각선의 기준에는 가로와 세로의 값의 합이 모두 동일하고, 왼쪽이 위에 있는 대각선의 기준에는 가로와 세로의 차이가 모두 동일하다.
개수는 각각 2n-1 개가 나오고, 이를 표시해주는 1차원 배열을 각각 사용해서 문제를 해결한다. 


계산 시간은 대략 배열의 크기를 n 이라고 하면 위의 방식은 3n, 내가 한 방식은 3n2이 나오는 것 같다.
아마 백 트래킹을 사용하는 도중에 알고리즘에서, 전체 복잡도가 얼마나 나오는지는 모르겠지만 O(a) 라고 하면,
O(a*n) vs O(a*n2)  정도 차이가 나서 속도 문제가 발생하는 것으로 판단된다. 

종합적으로 정답 코드도 숫자가 커질수록 엄청나게 느려졌는데, 정답 기준 시간인 10초 내외로 n이 14일때까지는 충분해서 
이렇게 풀라고 낸 것 같다. 

>> 정답

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
#include <iostream>
using namespace std;
 
int answer = 0;
int arr_size = 0;
// 세로에 값이 존재하는지 확인하기 위한 행렬
int* existing_site_arr;
// 우측 대각선에 값이 존재하는지 확인하기 위한 행렬
int* cross_right_up;
// 좌측 대각선에 값이 존재하는지 확인하기 위한 행렬
int* cross_left_up;
 
void dfs(int depth) {
    // if dfs depart end point, then stop;
    if (depth == arr_size ) {
        answer++;
        return;
    } 
 
 
    // go to the next level;
    for (int i = 0; i < arr_size; i++) {
        if ((existing_site_arr[i] == 1) || (cross_right_up[depth + i] == 1) || (cross_left_up[arr_size - 1 + (depth - i)] == 1))
            continue;
 
        existing_site_arr[i] = cross_right_up[depth + i] = cross_left_up[arr_size - 1 + (depth - i)] = 1;
        dfs(depth + 1);
        existing_site_arr[i] = cross_right_up[depth + i] = cross_left_up[arr_size - 1 + (depth - i)] = 0;
    }
}
 
int main() {
    cin >> arr_size;
 
    // 동적 할당을 이용하여, 이중 배열을 생성해준다. 
    existing_site_arr = (int*)malloc(sizeof(int) * arr_size); 
    cross_right_up = (int*)malloc(sizeof(int) * (2 * arr_size - 1));
    cross_left_up = (int*)malloc(sizeof(int) * (2 * arr_size - 1));
 
    dfs(0);
 
    cout << answer;
 
    return 0;
}
cs

>> 실패한 소스코드

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
using namespace std;
 
int answer = 0 ;
int arr_size = 0 ;
int** existing_site_arr;
 
void dfs(int depth, int column ) {
 
    // 배열 초기화 
    for (int i = depth; i < arr_size; i++) {
        for (int j = 0; j < arr_size; j++) {
            existing_site_arr[i][j] = 0;
        }
    }
      
    // 현재 말의 위치에서 갈 수 있는 곳에 말이 있는지 없는지 검사한다. 
    // >> 가로 & 세로 
    for (int i = 0; i < arr_size; i++) {
        if (existing_site_arr[depth][i] == 1) return; 
        if (existing_site_arr[i][column] == 1) return; 
    }
 
    // >> 좌대각선
    for (int i = 0; i < arr_size; i++) {
        if (!(( 0 <= depth - i && depth - i  < arr_size) && (0 <= column - i && column - i  < arr_size))) break;
        if ( existing_site_arr[depth-i][column-i] == 1) return;
    }
    for (int i = 0; i < arr_size; i++) {
        if (!((0 <= depth + i && depth + i < arr_size) && (0 <= column + i && column + i < arr_size))) break;
        if (existing_site_arr[depth + i][column + i] == 1) return;
    }
 
    // >> 우대각선
    for (int i = 0; i < arr_size; i++) {
        if (!((0 <= depth + i && depth + i < arr_size) && (0 <= column - i && column - i < arr_size))) break;
        if (existing_site_arr[depth + i][column - i] == 1) return;
    }
    for (int i = 0; i < arr_size; i++) {
        if (!((0 <= depth - i && depth - i < arr_size) && (0 <= column + i && column + i < arr_size))) break;
        if (existing_site_arr[depth - i][column + i] == 1) return;
    }
 
 
    // 통과하면 위치 입력 
    existing_site_arr[depth][column] = 1;
 
    // go to the next level;
    if (depth == arr_size - 1) {
        answer++;
        return;
    }
 
    for (int i = 0; i < arr_size; i++) {
        dfs(depth + 1 , i );
    } 
}
 
int main() {
 
    cin >> arr_size; 
 
    // 동적 할당을 이용하여, 이중 배열을 생성해준다. 
    existing_site_arr = (int**)malloc(sizeof(int*) * arr_size);
    for (int i = 0; i < arr_size; i++) {
        existing_site_arr[i] = (int*)malloc(sizeof(int) * arr_size);
    }
 
    // 배열 초기화 
    for (int i = 0; i < arr_size; i++) {
        for (int j = 0; j < arr_size; j++) {
            existing_site_arr[i][j] = 0;
        }
    }
 
    for ( int i = 0 ; i < arr_size ; i ++){
        // dfs 를 통하여 문제를 해결해준다. 
        dfs(0, i);
    }
 
    cout << answer; 
 
    return 0; 
}
cs



Search