[백준 9663] N-Queen

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

9663번: N-Queen

 

N-Queen 문제 패턴이 N과 M 문제와 비슷

백트래킹 및 재귀를 쓴다는 것, isused배열을 쓴다는 

그리고 isused 배열로 시간 복잡도를 O(M)에서 O(1)로 줄였다

 

바킹독님 코드 참고) https://blog.encrypted.gg/945

[실전 알고리즘] 0x0C강 - 백트래킹

 

그래서 정답 코드는

// 바킹독님 코드 참고
// https://blog.encrypted.gg/945
#include <iostream>

using namespace std;
bool isused1[40];
bool isused2[40];
bool isused3[40];

int cnt=0;
int n;
void func(int cur){
    if(cur==n){
        cnt++;
        return;
    }

    for(int i=0; i<n;i++){
        if(isused1[i]||isused2[i+cur]||isused3[cur-i+n-1])
            continue;
        isused1[i]=1;
        isused2[i+cur]=1;
        isused3[cur-i+n-1]=1;
        func(cur+1);
        isused1[i]=0;
        isused2[i+cur]=0;
        isused3[cur-i+n-1]=0;

    }
}

int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
func(0);
cout<<cnt;



}

재귀&백트래킹은 어려워...ㅠㅠ