[백준] 9663-N-Queen(C++)

문제링크:https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

dfs문제이고 백트래킹에서 대표적인 문제입니다.

15X15체스판까지 가능합니다. 

하지만 dfs 구현시 함수에서 NxN번 반복하면 당연히 시간초과입니다.  

다른방법을 생각해야합니다.

 

퀸은 자기의 양옆과 대각선 모두 이동이 가능합니다. 즉 행단위로 검사해도 괜찮습니다. 어차피 퀸이 있는 행에는 퀸이 있을 수 없기떄문입니다. 그렇기 때문에 열값은 count값을 사용합니다. ( 퀸이 체스판에 있을때마다 1씩증가)

 

n=4라면 답은 2입니다.

 

0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

 

 

 

 

우선 정답코드입니다.

#include <iostream>
using namespace std;

int n = 0, result  = 0;
bool visited[15][15] = { 0 };

bool available(int i, int cnt) {

	int x, y;
	for (x = 0; x < cnt; x++) {
		if (visited[i][x]) return false;
	}

	for (x = cnt - 1, y = i - 1; y >= 0; x--, y--) {
		if (visited[y][x]) return false;
	}

	for (x = cnt - 1, y = i + 1; y < n; x--, y++) {
		if (visited[y][x]) return false;
	}

	return true;
}

void dfs(int cnt) {

	if (cnt == n) {
	
		result++;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i][cnt] && available(i, cnt)) {

			visited[i][cnt] = 1;
			dfs(cnt + 1);
			visited[i][cnt] = 0;
		}
	}

	

}
int main(){

	cin >> n;

	dfs(0);
		
	cout << result << endl;

	return 0;
}

 

 

아래가 재귀루트입니다.

for (int i = 0; i < n; i++) {
		if (!visited[i][cnt] && available(i, cnt)) {

			visited[i][cnt] = 1;
			dfs(cnt + 1);
			visited[i][cnt] = 0;
		}
	}

 

행은 0~n-1 까지 이동하며 검사하고 열값은 체스판에 퀸을 올려놓을때 마다 1씩증가하며 위치를 찾습니다. 

 

 

아래는 검사함수입니다.

bool available(int i, int cnt) {

	int x, y;
	for (x = 0; x < cnt; x++) {
		if (visited[i][x]) return false;
	}

	for (x = cnt - 1, y = i - 1; y >= 0; x--, y--) {
		if (visited[y][x]) return false;
	}

	for (x = cnt - 1, y = i + 1; y < n; x--, y++) {
		if (visited[y][x]) return false;
	}

	return true;
}

 

 

자신의 왼쪽에 퀸이 있는지 확인하는 과정입니다.