[백준] 9663번 - N Qeen / C++

문제

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

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

 

입력

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

 

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

코드

#include <iostream>

using namespace std;

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

void dfs(int n)
{
	int i, j;

	if (n > N)
	{
		answer++;
		return;
	}
	for (i = 1; i <= N; i++)
	{
		board[n] = i;
		for (j = 1; j < n; j++)
		{
			if (board[j] == i || abs(n - j) == abs(i - board[j]))
			{
				board[n] = 0;
				break;
			}
		}
		if (board[n])
			dfs(n + 1);
	}
}

int main()
{
	cin >> N;
	dfs(1);
	cout << answer << endl;
	return 0;
}

 

dfs()에서 n번째 행의 i번째 열에 퀸을 놓는 것이 가능한지 확인한다.

n번째 행의 i번째 열에 퀸을 놓았을 때, 1행부터 n - 1행까지 놓은 퀸과 같은 열이나 대각선의 위치에 있게 되면 i번째 열에 퀸을 놓을 수 없다.

한 행에 하나씩 퀸을 놓았을 때, 모든 퀸이 같은 열이나 대각선의 위치에 있지 않은 배치를 찾으면 answer를 1만큼 증가시킨다.

 

링크

9663번: N-Queen

inbdni/Baekjoon