카테고리 없음

백준 9663번 : N-Queen

김진우 개발일지 2025. 2. 2. 18:15

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool isValid(int row, int col, const vector<int>& queen) {
    for (int i = 0; i < row; i++) {
        if (queen[i] == col || abs(queen[i] - col) == row - i)
            return false;
    }
    return true;
}

void solve(int row, int n, vector<int>& queen, int& count) {
    if (row == n) {
        count++;
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, queen)) {
            queen[row] = col;
            solve(row + 1, n, queen, count);
        }
    }
}

int main() {
    int n, count = 0;
    cin >> n;
    vector<int> queen(n, -1);
    solve(0, n, queen, count);
    cout << count << '\n';
}