9663번: N-Queen (BOJ C/C++)

9663번: N-Queen

사용 언어: C++

 

문제

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

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

입력

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

출력

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

 

풀이

(x,y)에 퀸을 놓으면 그 퀸이 존재하는 열, 우 대각선, 좌 대각선에 퀸(자신 및 다른 퀸)이 존재하는지에 대한 (true,false)를 배열들에 저장해서 재귀적으로 되고 안 되는 경우들을 탐색하다 cur==N인 베이스 조건에 도달하는 경우면 cnt+1이 되게 한다.

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

int N;
int cnt;

bool isused1[40]; //column에 퀸 있는지
bool isused2[40]; // / 방향 대각선 퀸 있는지
bool isused3[40]; // \ 방향 대각선 퀸 있는지

void func(int cur){
    if(cur == N){
        cnt++;
        return;
    }
    for(int i=0; i<N; i++){
        if(isused1[i] || isused2[i+cur] || isused3[cur-i+N-1])
            continue;
        isused1[i] = 1;
        isused2[i+cur] = 1;
        isused3[cur-i+N-1] = 1;
        func(cur+1);
        isused1[i] = 0;
        isused2[i+cur] = 0;
        isused3[cur-i+N-1] = 0;
    }
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    func(0);
    cout << cnt << '\n';

    return 0;
}