알고리즘 공부 및 문제 풀이/백준(BOJ)
[기출 상] E-Queen - 백트래킹
yoonjiy
2021. 9. 18. 00:29
[문제]
nqueen 문제의 변형으로 절대 놓을 수 없는 k개의 위치 정보가 추가로 주어질 때의 queen이 서로 공격할 수 없게 배치할 수 있는 경우의 수가 최대 몇 개인지를 리턴한다.
[코드]
#include <iostream>
using namespace std;
int col[16];
bool xy[14][14] = {false, };
int n, result;
bool check(int level)
{
for (int i = 0; i < level; i++)
if (col[i] == col[level] || abs(col[level] - col[i]) == level - i)
return false;
//col[i]: x좌표, i: y좌표. (x, y)와 (a, b)에 대해서 두 좌표가 대각선에 위치한다면 a-x == b-y.
return true;
}
void nqueen(int row)
{
if (row == n)
result++; // n번째 퀸을 놓으면 경우의 수 증가
else
{
for (int i = 0; i < n; i++)
{
col[row] = i;
if(xy[row][i]) //불가능한 곳에 놓으면 패스.
continue;
if (check(row))
nqueen(row + 1);
}
}
}
int main() {
cin >> n;
int k;
int x[14];
int y[14];
cin >> k;
for(int i=0; i<k; i++){
cin >> x[i];
}
for(int i=0; i<k; i++){
cin >> y[i];
}
for(int i=0; i<k; i++){
xy[x[i]-1][y[i]-1] = true;
}
nqueen(0);
std::cout << result;
}