BOJ 9663번 :: N-Queen

#작성 코드

#include <iostream>
#include <cstdio>
using namespace std;

int N;
int count;			// 퀸을 놓을 수 있는 방법의 수 
bool col[15];		// 인덱스 : 열의 번호. 이 열에 퀸이 존재하는가. 
bool *dup;
bool *ddown;

void findQueen(int n){
	if( n==N ){		// n은 행을 가리킴. 0~n-1까지 조사 완료했으면 
		count++;	// count 증가 
	}
	else{
		for(int i=0; i<N; i++){
			if( col[i] ) continue;
			if( dup[n+i] || ddown[N-1+n-i]) continue;
			col[i] = dup[n+i] = ddown[N-1+n-i] = true;
			findQueen(n+1);
			col[i] = dup[n+i] = ddown[N-1+n-i] = false;
		}
	} 
}

int main(){
	scanf("%d", &N);
	dup = new bool[2*N-1];
	ddown = new bool[2*N-1];
	
	findQueen(0);
	
	printf("%d", count);		// 퀸을 놓을 수 있는 방법의 수 출력 
	delete[] dup;
	delete[] ddown;
	return 0;
}

아래는 (n, i)위치에 퀸을 배치할 수 있는지 체크하는 함수를 사용한 코드인데, 아직 완성하지 못했다.

#include <iostream>
using namespace std;

int N;
int count;
bool *arr;
bool *dup;
bool *ddown;

//bool promising(int n, int i){
//	bool flag = true;
//	int k=0;
//	while( k<i && flag ){
//		if( arr[k]==true ) flag = false;
//		if( dup[n+k] == true || ddown[N-1+n-k]==true ) flag = false;
//	}
//	return flag;
//}

void findQueen(int n){
	if( n>=N ) count++;
	  
	for(int i=0; i<N; i++){		// (n, x)에 퀸을 배치할수있는지 체크
		if( arr[i]==true ) continue;
		if( dup[n+i] == true || ddown[N-1+n-i]==true ) continue;
		arr[i] = dup[n+i] = ddown[N-1+n-i] = true;
		findQueen(n+1);
		arr[i] = dup[n+i] = ddown[N-1+n-i] = false;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>N;
	
	arr = new bool[N];
	dup = new bool[2*N-1];
	ddown = new bool[2*N-1];
	
	findQueen(0);
	cout<<count;
	
	delete[] arr;
	delete[] dup;
	delete[] ddown;
	return 0;
}

##

findQueen 함수 내에서 현재 위치가 퀸을 놓기에 적절한 위치인지 promising함수로 체크하려고 했는데 이렇게 하면 (n, i)를 체크하면서 i에 따라 인덱스 0부터 i까지 체크하게 돼서 비효율적이다.

/ 방향 대각선은 행과 열의 합으로 구분할 수 있고,

\ 방향 대각선은 행-열이 n=3인 경우에 2, 1, 0, -1, -2 로 나타나므로 n-1을 더해주면 4, 3, 2, 1, 0으로 표현할 수 있다.