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를 넣어 가지치기를 해주었습니다.
