Algorithm/BOJ

N-Queen - 9663

jhg0406 2020. 3. 29. 16:17
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
//9663 - N-Queen
 
#include <iostream>
using namespace std;
 
int N;
bool r[15], c[15], dc[29], ic[29];
 
int di(int x, int y)
{
    return x - y + N-1;
}
 
int ii(int x, int y)
{
    return x+y;
}
 
int ch(int x, int y, int n)
{
    if(n == N-1)
        return 1;
    if(x == N)
        return 0;
    
    r[x] = c[y] = dc[di(x, y)] = ic[ii(x, y)] = true;
    int ret = 0;
    for(int i = 0; i<N; ++i)
        if(!r[x+1&& !c[i] && !dc[di(x+1, i)] && !ic[ii(x+1, i)])
            ret += ch(x+1, i, n+1);
    r[x] = c[y] = dc[di(x, y)] = ic[ii(x, y)] = false;
    return ret;
}
 
int main()
{
    cin >> N;
    int ans = 0;
    for(int i = 0; i<N; ++i)
        if(!r[0&& !c[i] && !dc[di(0, i)] && !ic[ii(0, i)])
            ans += ch(0, i, 0);
    cout << ans;
}
cs

 

 

 

 

 

 

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

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

 

 

 

 

N-Queen

가로, 세로, 감소하는 대각선, 증가하는 대각선에 겹치게 퀸이 존재할수 없기 때문에 각각의 배열을 만들어 해당 라인에 퀸이 있으면 true, 없으면 false를 넣어 가지치기를 해주었습니다.