[백준] 9663 N-Queen

 

유명한 N-Queen 문제다!

 

백트래킹을 통해 찾을 수 있다

 

여기서 핵심은 내가 한 행을 기준으로 보면 된다는 것이다

그럼 한 행을 잡고 그 안에서 퀸을 놓을 수 있는 열을 찾고 다음 행으로 가는 것이다

그렇게 행을 끝까지 도착하면 경우의수가 1개 증가한다!

 

소스코드

#include <iostream>
using namespace std;
int n,ans;
bool check[22][22];
int dx[2] = {-1,-1};
int dy[2] = {-1,1};
 
bool inner(int x,int y){
    return (0<=x && x<n && 0<=y && y<n);
}
bool can(int x,int y){
    for(int i=0;i<n;i++){
        if(check[i][y]) return false;
    }
    for(int i=0;i<2;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        while(inner(nx,ny)){
            if(check[nx][ny]) return false;
            nx+=dx[i]; ny+=dy[i];
        }
    }
    return true;
}
 
void solve(int pos){
    if(pos==n){
        ans++; return;
    }
 
    for(int i=0;i<n;i++){
        if(can(pos,i)) {
            check[pos][i]=true;
            solve(pos+1);
            check[pos][i]=false; 
        }
    }
}
 
int main(){
    scanf(" %d",&n);
    solve(0);
    printf("%d\n",ans);
}