백준 9663번 N-Queen

백준 9663번 N-Queen 문제이다.

백트래킹으로 가장 유명한 문제라고 할 수 있는 체스판에 퀸을 놓는 문제이다. 

이번 문제에서는 하나씩 놓아가면서 놓았을때 퀸이 놓일 수 있는 조건을 확인해서 놓도록 해주었다.

func 함수를 통해 재귀 방식으로 하나씩 놓아가도록 하였고 

promising 함수를 통해 놓는것이 가능한지 파악하였다. 

언어는 C++을 사용하였다.

 

#include <iostream>

using namespace std;
int n;
int result = 0;
int arr[15] = {0,};
bool promising(int i){
    for(int j = 0; j < i; j++){
    
        if(arr[i] == arr[j] || abs(arr[i] - arr[j]) == (i - j)){
            return false;
        }
    }
    
    return true;
}
void func(int cnt){
    if(cnt == n){
        result++;
    }
    else{
        for(int j = 0; j < n; j++){
            arr[cnt] = j;
            if(promising(cnt)){
                func(cnt+1);
            }
        }
    }
    
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin >> n;
    func(0);
    std::cout << result << '\n';
}

놓는것이 가능한지 확인하는 것은 같은 라인에 놓진 않았는지 대각선에 놓진 않았는지 확인해야하는데

대각선은 이전에 놓았던 퀸이 몇번째에 놓였는지와 현재 놓는것이 몇번째 놓는 건지를 파악하고

arr 배열의 값의 차이와 비교하면 대각선에 놓인건지를 확인할 수 있다.

성공!