백준 BOJ 9663 C++ [N-Queen]

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

int n, cnt;
// 문제 이해를 위해 배열 범위를 빡빡하게 잡음
bool col[14];       // 열에 대해
bool diag1[27];     // 우하향 대각선(\)에 대하여, 인덱스 범위 [-(n-1), n-1]에서 n-1을 더하여 [0, 2(n-1)]
bool diag2[27];     // 우상향 대각선(/)에 대하여, 인덱스 범위 [0, 2(n-1)]

// 하나의 행에는 반드시 하나의 퀸만 존재한다.
// 따라서 각 행에 대하여 퀸을 배치하는 열의 위치만 결정하면 된다.
void dfs(int i) {
    if (i == n) {  // 모든 행에 퀸을 배치한 경우
        cnt++;
        return;
    }
    for (int j = 0; j < n; ++j) {
        // 체스판에서 (i, j) 위치에 대하여 열과 두 대각선이 모두 비어있는 경우
        if (!col[j] && !diag1[i - j + n - 1] && !diag2[i + j]) {
            // 우하향 대각선에 대한 diag1에서 인덱스의 최댓값 n - 1을 더해주는 이유는 
            // 음수 인덱스가 발생하지 않도록 하며 인덱스 0부터 사용하기 위해서
            col[j] = diag1[i - j + n - 1] = diag2[i + j] = true;  // 방문 표시
            dfs(i + 1);
            col[j] = diag1[i - j + n - 1] = diag2[i + j] = false;  // 방문 표시 해제
        }
    }
}

void solve() {
    cin >> n;
    dfs(0);
    cout << cnt << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}