[C/C++ 백준 9663번] N-Queen (Gold 5)

www.acmicpc.net/problem/9663

9663번: N-Queen

정말 까다로웠던 문제.. 있는 그대로 구현하면 되기는 한다.

각 행마다 퀸을 채우는데, 채울 때마다 밑,  왼쪽아래 대각선, 오른쪽 아래 대각선에  방문하지 못하도록 채워주자. 이때 위의 행을 볼 필요 없으니 고려하지 말자(그 차이로 시간초과가 생기더라).

 

제한 시간이 10초로 넉넉하기 때문에, 브루트포스를 이용해 모든 경우를 조사해도 상관없다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N, ans=0;
bool array[16][16];
void func(int start){
	/*for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++)
			printf("%d ", array[i][j]);
		printf("\n");
	}
	printf("\n");*/
	if(start == N+1){
		ans++;
		return ;
	}
	bool ok = false;
	int cnt = 0;
	for(int i=1; i<=N; i++){
		if(!array[start][i]){
			ok = true;
			vector <pair<int, int>> v;			
			for(int j=start; j<=N; j++){
				if(array[j][i] == false){
					array[j][i]=true;
					v.push_back({j, i});
				}
			}
			cnt = 0;
			while(start+cnt<=N && i+cnt<=N){
				cnt++;
				if(array[start+cnt][i+cnt] == false){
					array[start+cnt][i+cnt] = true;
					v.push_back({start+cnt, i+cnt});
				}
				
			}
			cnt = 0;
			while(start+cnt<=N && i-cnt>=0){
				cnt++;
				if(array[start+cnt][i-cnt]==false){
					array[start+cnt][i-cnt] = true;	
					v.push_back({start+cnt, i-cnt});
				}	
			}
			func(start+1); cnt = 0;
			for(int i=0; i<v.size(); i++)
				array[v[i].first][v[i].second]=false;
		}
	}
	if(!ok)
		return;
}
int main(void){
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++)
			array[i][j] = false;
	}
	func(1);
	printf("%d", ans);
}