알고리즘/알고리즘 문제 풀이
(C++) 백준 9663번 - N-Queen
용꿀
2023. 4. 7. 00:40
문제 링크 : https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
풀이
백트래킹을 활용하여 풀이하였다.
Queen은 같은 행이나 열, 같은 대각선 상에 존재하면 서로를 잡을 수 있다는 점을 알아야 한다.
그렇기에 한 행에 놓으면 같은 행의 다른 칸에 놓을 수 없음을 이용하여 한 행에 Queen을 하나씩만 두고, 열과 대각선 상만 피해서 Queen을 놓게 구현하면 된다.
#include <iostream>
using namespace std;
int n;
int isUsedcol[15]; // 이미 들어간 행에 체크
int isUseddiagu[30]; // 이미 들어간 우측 상단으로 향하는 대각선에 체크
int isUseddiagl[30]; // 이미 들어간 우측 하단으로 향하는 대각선에 체크
int cnt;
void nq(int queen){
if(queen == n) { // base condition
cnt++;
return;
}
for(int i = 0; i < n; i++){
// 잡을 수 있는 위치에 이미 존재한다면 skip
if(isUsedcol[i] or isUseddiagu[i+queen] or isUseddiagl[queen-i+n-1]) continue;
isUsedcol[i] = 1;
isUseddiagu[i+queen] = 1;
isUseddiagl[queen-i+n-1] = 1;
nq(queen+1);
isUsedcol[i] = 0;
isUseddiagu[i+queen] = 0;
isUseddiagl[queen-i+n-1] = 0;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
nq(0);
cout << cnt;
}