백준 9663 N-Queen (백트래킹(가지치기), 재귀함수) - C++

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

재귀함수 문제이다.

맨 처음에 자료구조였나,, 이문제를 들었던 적이 있는데

그때는 나한테 너무나도 어렵게 느껴졌었는데

지금은 어떻게 풀어야하는 아이디어가 대략 있으니까 어렵지 않게 구현한 것 같다.

 

col[i] 는 우선 i번째 열의 행 값이다.(위에서부터 몇번째 행에 있는지)

1열부터 해서 값을 설정한 다음에, 그 다음열부터 이전 열들에 위치한 행값을 비교하면서 N번째까지 갔을 경우 1증가,

아닐시 false를 반환하고 끝내면 된다.

#include <iostream>
using namespace std;
int N;
int result=0;
int col[15];
 
bool ispossible(int i){
    for(int j=0; j<i; j++) {
        if (col[i] == col[j] || i - j == abs(col[i] - col[j]))
            return false;
    }
    return true;
 
}
 
void nqueen(int i){
    if(i==N)
        result++;
    else{
        for(int j=0; j<N; j++){
            col[i]=j;
            if(ispossible(i)){
                nqueen(i+1);
            }
        }
    }
}
 
int main(void){
    cin>>N;
    nqueen(0);
    cout<<result<<" ";
}