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

문제

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

 

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

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 15)

 

예제 입력

8

 

예제 출력

92

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

'퀸', '서로 공격할 수 없게', 그리고 '방법의 수'라는 것을 보고 이 문제는 단순 구현 문제라는 것을 알 수 있었다.

 

우선 첫 줄에 퀸을 어디에 놓느냐 그리고 다음 줄에 퀸을 어디에 놓느냐에 따라 그 다음줄에 놓을 수 있는 퀸이 놓여지지 않는 곳을 결정할 수 있다.

 

즉, 해당 위치에 퀸을 놓았을 때와 안 놓았을 때로 구분되는데 이러한 문제는 백트래킹으로 쉽게 풀 수 있다.

 

퀸이 공격하는 방향은 상, 하, 좌, 우, 대각선으로 해당 좌표에 퀸이 놓여지면 해당 좌표에서 공격할 수 있는 모든 좌표에다가 +1을 하면된다.

 

그리고 새롭게 퀸을 놓으려고 할 때 해당 좌표의 값이 1보다 큰 경우 퀸을 놓을 수 없게 되므로 좌표의 값이 0인 곳에서만 퀸을 놓고 N개의 퀸을 전부 다 놓았을 때 경우의 수를 +1 하면 되는 것이다.

 

코드

#include <iostream>

int board[15][15];
int N;

void fillBoard(int y, int x)
{
	board[y][x] += 1;
	for (int i = 0; i < N; i++)
	{
		if (i != y)
			board[i][x] += 1;
		if (i != x)
			board[y][i] += 1;
	}
	int tempY = y;
	int i = 1;
	while (tempY--)
	{
		if (x - i >= 0)
			board[tempY][x - i] += 1;
		if (x + i < N)
			board[tempY][x + i] += 1;
		i++;
	}
	tempY = y;
	i = 1;
	while (tempY != N)
	{
		if (x - i >= 0)
			board[tempY + 1][x - i] += 1;
		if (x + i < N)
			board[tempY + 1][x + i] += 1;
		tempY++;
		i++;
	}
}

void clearBoard(int y, int x)
{
	board[y][x] -= 1;
	for (int i = 0; i < N; i++)
	{
		if (i != y)
			board[i][x] -= 1;
		if (i != x)
			board[y][i] -= 1;
	}
	int tempY = y;
	int i = 1;
	while (tempY--)
	{
		if (x - i >= 0)
			board[tempY][x - i] -= 1;
		if (x + i < N)
			board[tempY][x + i] -= 1;
		i++;
	}
	tempY = y;
	i = 1;
	while (tempY != N)
	{
		if (x - i >= 0)
			board[tempY + 1][x - i] -= 1;
		if (x + i < N)
			board[tempY + 1][x + i] -= 1;
		tempY++;
		i++;
	}
}

bool checkBoard(int y, int x)
{
	if (board[y][x] >= 1)
		return false;
	return true;
}

int dp(int queen)
{
	if (queen == N)
		return 1;
	int ret = 0;
	for (int i = 0; i < N; i++)
	{
		if (checkBoard(i, queen))
		{
			fillBoard(i, queen);
				ret += dp(queen + 1);
			clearBoard(i, queen);
		}
	}
	return ret;
}

int main(void)
{
	std::cin >> N;
	std::cout << dp(0) << std::endl;
}

문제 출처

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

9663번: N-Queen