[백준] 9663 N-Queen c++

 

문제 링크 https://www.acmicpc.net/problem/9663

KEY

• 퀸을 서로 공격하지 않게 하기 위해서는 퀸을 같은 행, 열, 대각선에 놓지 않아야 한다.<조건>
• (0~마지막 행) 까지 모든 행을 조사하면서 <조건>에 맞는 퀸의 위치가 나올 경우 다음 행으로 넘어간다.
• 만약에 <조건>에 맞지 않을 경우 현재 행의 다음 열로 가서 <조건>에 부합하는지 확인한다.

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 15;
int n;
int cnt = 0;
int arr[MAX];
 
bool check(int row) {
    for (int i = 0; i < row; i++) { //여태까지 놓았던 퀸들과 같은 열에 있거나, 대각선에 있으면 놓을수없음.
        if ((arr[i] == arr[row]) || (row - i == (abs(arr[row] - arr[i])))) {
            return false;
        }
    }
    return true;
}
void dfs(int row) {
    if (row == n) { //마지막 행까지 오면 카운트 증가
        cnt++;
        return;
    }
    for (int col = 0; col < n; col++) { //현재 행에서 모든 열 검사
        arr[row] = col;
 
        if (check(row)) {
            dfs(row + 1);
        }
    }
}
int main(void) {
    cin >> n;
    dfs(0);
    cout << cnt;
}