[BOJ]9663 N-Queen

• N-Queen
  • 아주 유명한 백트래킹 + 완전탐색 문제
  • 아래 조건을 만족하며 퀸을 N X N 보드에 배치해야한다.
    • 1. 가로 배치 체크는 자동으로 수행
    • 2. 세로 배치 체크
    • 3. 대각선 배치 체크
    • 조건1: 퀸끼리는 가로상으로 만나면 안된다.
    • 조건2: 퀸끼리는 세로상으로 만나면 안된다.
    • 조건3: 퀸끼리는 대각선상으로 만나면 안된다.
• 풀이
  • row: 현재 퀸을 놓을 x좌표
  • col: 현재 퀸을 놓을 y좌표
  • i : 이전에 퀸을 놓은 x좌표
  • board[i] : 이전에 퀸을 놓은 y좌표
  • 1. x(row)를 기준으로 하나씩 퀸을 놓아간다.
  • 2. 퀸을 놓을 수 있는지 위 조건을 통해 체크한다.
  • 이를 모든 경우에 대해 반복한다.

#include <bits/stdc++.h>
using namespace std;
int N, ans = 0;
vector<int> board(16, -1);
bool check(int row, int col){
    for(int i = 0; i < row; ++i){
        if(board[i] == col || abs(row - i) == abs(col - board[i])){
            return false;
        }
    }
    return true;
}
void N_Queen(int row){
    if(row == N){//모든 체스말 선택 완료
        ++ans;
        return;
    }
    for(int col = 0; col < N; ++col){
        if(check(row, col)){
            board[row] = col;
            N_Queen(row+1);
            board[row] = -1;
        }
    }
}
int main(){
    cin >> N;
    N_Queen(0);
    cout << ans;
    return 0;
}