백준 9663: N-Queen

문제 요약

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

문제 분류

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

문제 풀이

nxn의 2차원 배열이지만, 1차원 배열로도 해결 가능하다. 최대크기가 15인 1차원 배열을 선언하고, 각 값에는 높이에 해당하는 값을 할당함으로써 퀸을 놓는것으로 본다. 예를들어, ary[0]에 1이 입력되었다면, (0,1)의 위치에 퀸을 놓은 것이다. 다만 퀸이 없는 경우는 0이므로 퀸을 놓을 때는 1부터 세야 한다.

퀸은 각 행당 하나씩 놓으면 되므로 어느 열에 놓을지만 결정해주면 된다. 여기 dfs함수에서 val이 행이고 idx는 열이다. 즉, val이 n과 같아질때 카운트를 하면 되고, idx의 위치에 삽입 가능한지만 확인하고 탐색하면 된다.

삽입 가능성에 대해서는 두 가지가 만족되어야하는데, 해당 열에 퀸이 놓여있지 않을 것. 즉, ary[idx] == 0이어야 하며, 두 번째로 대각선 위치에 퀸이 놓여져있지 않은가를 판단해야 하는데, 이것은 valid()를 통해 해결해주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int ary[15];
int n, cnt = 0;

bool valid(int idx, int val) {
	for (int i = 0; i < n; i++) {
		if (ary[i] != 0)
			if (max(idx - i, i - idx) == max(val - ary[i], ary[i] - val))
				return false;
	}
	return true;
}

void dfs(int idx, int val) {
	ary[idx] = val;
	if (val == n) cnt++;
	for (int i = 0; i < n; i++) {
		if (ary[i] == 0 && valid(i, val + 1))
			dfs(i, val + 1);
	}
	ary[idx] = 0;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		dfs(i, 1);
	printf("%d", cnt);
	return 0;
}