백준 9663 - N Queen

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

9663번: N-Queen

문제 설명

---

N이 주어졌을때, N*N 체스판에서 N개의 퀸의 이동 방향이 서로 겹치지 않고 N개 모두 배치될 수 있는 경우의 수를 구하는 문제

 

 

접근 방법

---

백트래킹, DFS를 이용한 문제입니다. 가능성이 없는 경우의 수를 배제하면서 풀이를 진행하시면 됩니다.

이 문제에서 가장 중요한 것은 퀸이 상,하,좌,우, 대각선을 모두 움직일 수 있으므로 퀸은 하나의 행의 하나 또는 하나의 열의 하나만 존재할 수 있습니다. 나아가 대각선에 적용되는 공식을 발견하여 적용하면 간단하게 풀이 가능합니다.~

 

 

코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n,ans=0;
int visit[16];
bool _Condition(int chk){
    for(int i=0;i<chk;i++){
        if(visit[i]==visit[chk]|| abs(visit[chk]-visit[i])==(chk-i)) return false;
    }
    return true;
}
void nQueen(int start){
    if(start==n) ans++;
    else{
        for(int i=0;i<n;i++){
            visit[start]=i;
            if(_Condition(start)){nQueen(start+1);}
        }
    }
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    nQueen(0);
    cout<<ans<<"\n";
    return 0;
}

funny algorithms ^&^~