N-Queen (중요!)

https://www.acmicpc.net/problem/9663

9663번: N-Queen

체스판에 놓을 지 말지 -> 2 ^ (N * N)  -> 너무 크다!!

한 개의 행에 놓으면 끝, 한 개의 열에 놓으면 끝  --> N!

calc(0)  -> 모든 열을 for문으로 조사

for문 안에서 재귀로 다음 행으로 갈 수 있는지 check한다

check 방법 -> 같은 열에 있는지 확인, 왼쪽 대각선 위, 오른쪽 대각선 위 확인

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool a[15][15];
int n;
int ans = 0;
 
// row 행 col 열
bool check(int row, int col) 
{
    // 같은 행에 있는지 확인 있으면 false
    for (int i = 0; i <= row; i++)
    {
        if (i == row) continue;
        if (a[i][col])
            return false;
    }
// 대각선 왼쪽
    int x = row - 1;
    int y = col - 1;
    while (x >= 0 && y >= 0)
    {
        if (a[x][y] == true)
            return false;
 
        x -= 1;
        y -= 1;
    }
//대각선 오른쪽
    x = row - 1;
    y = col + 1;
    while (x >= 0 && y < n)
    {
        if (a[x][y] == true)
            return false;
 
        x -= 1;
        y += 1;
    }
 
    return true;
}
 
void calc(int row) 
{    
    if (row == n)
        ans += 1;
 
    // 한개의 행에 대해서 열을 체크
    for (int col = 0; col < n; col++)
    {
        a[row][col] = true; // 여기에 놓고
        if (check(row, col))
            calc(row + 1);
        a[row][col] = false; // 브루트포스니까 끝나면 false 처리
    }
}
 
int main()
{
    cin >> n;
    calc(0);
    cout << ans << '\n';
    return 0;
}