728x90
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
코드
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
int N;
int ans = 0;
int col[16];
bool temp;
void nqueen(int x) {
if(x==N){
ans++;
return;
}
for(int i=0; i<N; ++i){
temp = true;
col[x] = i;
for(int j=0; j<x; ++j){
if(col[x] == col[j] || (abs(x-j) == abs(col[x]-col[j]))){
temp = false;
break;
}
}
if(temp){
nqueen(x+1);
}
}
}
int main() {
cin >> N;
nqueen(0);
cout << ans;
return 0;
}
문제만 보면 간단한거 같으면서도...? 쉽지 않은 문제이다.
나는 처음 이 문제를 보자마자 무식하게 이차원 배열의 모든 좌표에 퀸을 놓았을 때 겹치지 않을 때의 경우의 수를 구하려 했다.
그래서 0,0 부터 N,N까지 퀸을 대입해보면서 풀려 하였는데 막상 해보니 쉽게 나오질 않았다...
1시간의 사투 결과 힌트를 보게 되었다....
위 그림과 같이 퀸이 겹치지 않는 경우의 수를 곰곰히 생각해보면,
1. 한 줄에 퀸을 한개만 놓을 수 있다.
2. 대각선으로 퀸이 겹치면 안된다.
이 두가지 수만 충족시키면 퀸의 배치가 완성된다.
1번의 경우 구하기 쉽고 2번이 문제인데 2번은 (x좌표의 차이 == y 좌표의 차이) 이렇게 풀면 쉽게 풀린다.
문제를 풀어보기 전에 한번 생각해보는 시간을 가져보자!
728x90
반응형
'PS > 재귀' 카테고리의 다른 글
[14499] 주사위 굴리기 (1) | 2023.07.10 |
---|---|
[14889] 스타트와 링크 (0) | 2023.03.26 |
[15652] N과 M(3) (0) | 2023.03.21 |
[15651] N과 M(3) (0) | 2023.03.21 |
[15650] N과 M (2) (0) | 2023.03.21 |