[BOJ 9663] N-Queen

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

백트레깅 너무 어렵당. 백트레킹과 완전탐색의 차이라고 한다면 alpha beta pruning 처럼 백트레킹에는 커팅되는 과정이 추가된다고 생각할수 있을꺼 같다 (뇌피셜 ) 모든 경우를 다해보지 않고 일단 각 행에는 1개씩은 queen이 존재할 수 있으므로 모든행까지 다 가는 경우는 완성할 수 있는 경우의 수가 +1이 된다.

각각의 배열 3개를 통해서 해당 퀸이 같은 열이 있는지, 같은 대각선 1,2에 있는지를 상수시간에 확인할 수 있다. 어렵당

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
typedef long long ll;
 
using namespace std;
 
int n,arrCol[55],arrDe1[55],arrDe2[55],ans;
 
bool chk(int y,int x){
    if(arrCol[x] == 1)
        return false;
    if(arrDe1[y+x] == 1)
        return false;
    if(arrDe2[n+y-x] == 1)
        return false;
    
    return true;
}
 
 
void solve(int c){
    if(c == n){
        ans++;
        return;
    }
    for(int i=0;i<n;i++){
        if(chk(c,i)){
            arrCol[i] = 1;
            arrDe1[c+i] = 1;
            arrDe2[n+c-i] = 1;
            solve(c+1);
            arrCol[i] = 0;
            arrDe1[c+i] = 0;
            arrDe2[n+c-i] = 0;
        }
    }
}
 
int main(){
    ans = 0;
    scanf("%d" , &n);
    solve(0);
    cout <<ans <<endl;
    return 0;
}