N-Queen C++ - 백준 9663

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

백트래킹의 고유명사.

문제 접근

한 행에 두개의 퀸이 존재 할 수 없기 때문에,

N퀸 문제는 일차원 배열으로 해결할 수 있다.

놓을 수 있는지 판단하는 check 함수로 대각선, 열이 같은지

확인해주는 것이 핵심이었다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n;
long long ans=0;

bool check(int cnt, int ind, int arr[15]){
    //(cnt,ind) -> position
    //(i,arr[i])
    for(int i=0;i<cnt;i++){
        if(arr[i]==ind) return false;
        if(abs(i-cnt)==abs(arr[i]-ind)) return false;
    }
    return true;
}

void solve(int cnt, int arr[15]){
    if(cnt==n){ans++;return;}
    for(int i=0;i<n;i++){
        if(check(cnt,i,arr)){
            int tmp[15];
            for(int i=0;i<cnt;i++) tmp[i]=arr[i];
            tmp[cnt]=i;
            solve(cnt+1, tmp);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    int arr[15]; memset(arr,0,sizeof(arr));
    solve(0,arr);
    cout << ans;
    return 0;
}