(백준 c++) 9663 N-Queen

문제

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

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

입력

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

출력

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

 

 

DFS를 배우기 좋은 N-Queen 문제.

현재 위치에 퀸을 놓을 수 있는지 확인하는 isTrue 함수

이 함수를 이용해 해당하는 위치에 퀸을 놓고 DFS를 통해 N개의 퀸을 놓을 수 있는 경우의 수를 구하면 된다.

isTrue는 현재 위치에서 팔방향으로 뻗는 자리를 모두 검사하여 true(퀸이 놓여 있는 경우)가 아니면 true를 리턴한다.

true가 리턴되면 그 자리에 퀸을 놓고, 계속 진행하면 된다.

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

using namespace std;

bool visited[15][15] = {false, };
int N = 0, ans = 0;

void dfs(int, int, int);
bool isTrue(int, int);

void dfs(int row, int col, int count)
{
	if(count == N)
	{
		ans++;
		return;
	}
	
	for(int i = 0; i < N; i++)
	{
		if(isTrue(row, i))
		{
			visited[row][i] = true;
			dfs(row + 1, i, count + 1);
			visited[row][i] = false;
		}
	}
}

bool isTrue(int row, int col)
{
	//가로 검사
	for(int i = 0; i < N; i++)
	{
		if(visited[row][i])
			return false;
	}
	//세로 검사
	for(int i = 0; i < N; i++)
	{
		if(visited[i][col])
			return false;
	}
	//우측 상방 검사
	for(int i = row, j = col; i >= 0 && j < N; i--, j++)
	{
		if(visited[i][j])
			return false;
	}
	//우측 하방 검사
	for(int i = row, j = col; i < N && j < N; i++, j++)
	{
		if(visited[i][j])
			return false;
	}
	//좌측 상방 검사
	for(int i = row, j = col; i >= 0 && j >= 0; i--, j--)
	{
		if(visited[i][j])
			return false;
	}
	//좌측 하방 검사
	for(int i = row, j = col; i < N && j >= 0; i++, j--)
	{
		if(visited[i][j])
			return false;
	}
	return true;
}
	
int main() {
	scanf("%d", &N);
	dfs(0, 0, 0);
	
	cout << ans;
	return 0;
}