자료구조 및 알고리즘/백준
[백준 9663] N-Queen
아기사우르스
2023. 4. 6. 15:23
728x90
https://www.acmicpc.net/problem/9663
N-Queen 문제 패턴이 N과 M 문제와 비슷
백트래킹 및 재귀를 쓴다는 것, isused배열을 쓴다는
그리고 isused 배열로 시간 복잡도를 O(M)에서 O(1)로 줄였다
바킹독님 코드 참고) https://blog.encrypted.gg/945
그래서 정답 코드는
// 바킹독님 코드 참고
// 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;
}
재귀&백트래킹은 어려워...ㅠㅠ
728x90