백준 9663 N-Queen

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

N-Queen 문제입니다. N*N의 체스판이 주어졌을때 각행마다 하나의 퀸이 각각 다른퀸들의 영역에 침범하지 않고 놓여질 수 있는 경우의 수를 찾는 문제입니다. 전형적인 백트래킹 문제이며 저는 재귀함수를 이용한 dfs를 이용하여 풀었습니다. 

 

먼저 N-Queen 문제 같은경우 행에 대해서는 신경을 쓸 필요가 없습니다. 그행에 퀸을 놓으면 아래 행으로 넘어가면 되므로 신경 써줘야 할 부분은

열과 우측으로 향하는 대각선 좌측으로 향하는 대각선 총 3가지입니다. 

 

열 같은 경우 1차원 배열을 하나 지정하여 퀸이 놓여진 열은 다른 퀸이 놓일 수 없도록 지정해주면 됩니다.

 

좌측으로 향하는 대각선의 경우 두 좌표의 x,y 값의 합이 항상 동일합니다. 예를들어 4,4를 기준으로하면 5,3 6,2 7,1 이런식으로 내려가고 3,5 2,6 1,7 이런식으로 올라가므로 항상 합이 8이 됩니다. 따라서 이부분을 조건검사를 해주면 됩니다.

 

우측으로 향하는 대각선의 경우 x,y 좌표가 1씩 늘어나거나 1씩 줄어드므로 그차이가 항상 일정합니다. 따라서 그차이가 -15~15까지 존재할 수 있으므로

배열의 인덱스로 사용하기 위해 N을 더해주어 0~30 까지로 사용을 하였습니다.

 

이렇게 조건을 검사해주며 dfs를 진행해주고 마지막 행까지 퀸이 놓이면 경우의수를 증가시켜주면 문제가 해결됩니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <cmath>

using namespace std;

int column[16];
int rightline[32];
int leftline[32];
int N;
int num;

void dfs(int k) {
	
	if(k == N) {
		num++;
		return;
	}
	
	for(int i = 0; i < N; i++) {
		if(!column[i] && !rightline[N+ (k-i)] && !leftline[k+i]) {
			column[i] = 1;
			rightline[N+ (k-i)] = 1;
			leftline[k+i] = 1;
			dfs(k+1);
			column[i] = 0;
			rightline[N+ (k-i)] = 0;
			leftline[k+i] = 0;
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N;
	
	dfs(0);
		
	cout<<num;
}