백준 9663번: N-Queen

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

9663번: N-Queen

 

 

0. 알고리즘 분류

 브루트포스 알고리즘, 백트래킹

 

 

1. 문제

 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

 

2. 풀이

 처음 봤을 때, 어떻게 풀지 감이 잡히지 않아 알고리즘 분류를 봤다. 브루트포스. 완전 탐색. 그냥 전부 돌리면 된다고 한다. 주어진 시간은 넉넉하게 10초. N * N의 체스판에서 퀸은 0/45/90/135/180/225/270/315/360도 방향으로 끝까지 움직일 수 있다. 그래서 우선, N * N의 거대한 체스판을 만들고, 퀸이 (x, y) 좌표에 있을 때, 해당 퀸이 공격할 수 있는 좌표들을 전부 체크하기로 했다. 좌측부터 가능한 좌표에 퀸을 놓으면서 공격할 수 있는 좌표를 전부 체크하고, 공격할 수 없는 자리에 퀸을 놓는 것을 반복한다. x좌표가 7인, 체스판의 끝에 도달하면, 경우의 수 ans에 1을 더해준다. 이후, 해당 경로는 이미 탐색된 것이므로, 체크된 좌표들을 해제시켜준다. 이것이 백트래킹이다. 이것을 끝까지 반복하면 된다.

 

 가능한 좌표를 체크하는 방법은, 해당 좌표 배열에 +1을 해주는 것이다. 백트래킹을 할 때는 -1을 해준다. 이는 퀸들이 공격 가능한 좌표가 중복될 수 있기에, 가점 방식으로 바꾼 것이다.

 

 어떻게 풀지는 생각해냈지만, 구현이 상당히 오래 걸렸다. 내가 재귀함수에 약하기도 하고. 

 

 

3. 코드

#include <iostream>

using namespace std;

int chess[15][15];
int n;
int ans = 0;
int dir[3][2] = {
	{1, -1},
	{1, 0},
	{1, 1} };

void visit(int x, int y, int yes) {
	for (int i = x+1; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			int _x = x + (i-x)*dir[j][0];
			int _y = y + (i-x)*dir[j][1];
			
			if (_y < 0 || _y >= n) {
				continue;
			}
			chess[_y][_x] += yes;
		}
	}
}
	
void func(int x, int y) {
	if (x == n-1) {
		ans++;
		
		return;
	}
	
	visit(x, y, -1);
	
	for (int i = 0; i < n; i++) {
		if (x+1 < n && chess[i][x+1] > 0) {
			func(x+1, i);
			visit(x+1, i, 1);
		}
	}
}

int main(void) {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			chess[i][j] = 1;
	}
	
	for (int i = 0; i < n; i++) {
		func(0, i);
		visit(0, i, 1);
	}
	
	printf("%d", ans);
	return 0;
}