[BOJ] N-Queen 9663번 C++

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

접근 방법

 

퀸은 다음과 같이 이동이 가능하다

따라서 한 퀸이 한 row에 위치해있다면 그 row와 대각선 두개에 다른 퀸을 둘 수 없다

이를 활용해 세 개의 불리언 배열을 사용해 위치할 수 있는 퀸의 경우의 수를 구할 수 있다

이때 대각선을 구하는 방정식이 중요한데

하나는 x+y이고 하나는 x+y-N+1으로 설정해주면 된다!!

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int N, cnt = 0;
bool usedRow[30];
bool usedDiag[30];
bool usedDiag2[30];

int mat[17][17];

void sol(int x) {
    if(x == N) {
        cnt++;
        return;
    }

    for(int y=0; y<N; y++) {
        if(usedRow[y] || usedDiag[x + y] || usedDiag2[x - y + N - 1]) continue;
        usedRow[y] = true;
        usedDiag[x + y] = true;
        usedDiag2[x - y + N - 1] = true;
        sol(x + 1);
        usedRow[y] = false;
        usedDiag[x + y] = false;
        usedDiag2[x - y + N - 1] = false;
    }
}

int main() {
    cin>>N;
    sol(0);
    cout<<cnt;

}