N-Queen <실패>
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 128 MB | 11008 | 6361 | 4141 | 57.626% |
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제 입력 1 복사
1
8
예제 출력 1 복사
1
92
풀이 <다시풀기>
- 시간 초과 해결하기
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
#include <iostream>
#include <vector>
#include <math.h>
#define IOFAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int check[16][16];
int n,result;
using namespace std;
bool IsQueen(int ny,int nx){ // 체크되어있는 좌표가 대각선이 아니고, 같은 좌표값도 아닐때
for(int i=1;i<ny;i++){
if(check[i][nx]==1) //x가 같으면 (y는 같을 수 없음)
return false;
for(int j=1;j<=n;j++){
if(check[i][j]==1){
if(abs(ny-i) == abs(nx-j))
return false;
}
}
}
return true;
}
void dfs(int y){ //1,(1,2,3~)
if(y==n){
++result;
return;
}
for(int i=1;i<=n;i++){ // x
if(IsQueen(y+1,i)){
check[y+1][i]=1;
dfs(y+1);
check[y+1][i]=0;
}
}
}//dfs
int main(){
IOFAST();
cin >> n;
for(int i=1;i<=n;i++){ // x
check[1][i]=1;
dfs(1); //y좌표
check[1][i]=0;
}
cout << result << '\n';
}