백준 C++ - N-Queen (브루트포스, 백트래킹)

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

9663번: N-Queen

1. 한 행에 퀸 하나!

    - 한 행에 퀸이 없다면 다른 행에 퀸을 두 개 이상을 놓아야 하기 때문에 한 행에 퀸 하나라는 규칙을 지키며 풀었다. 

 

2. (1, 1)에서 퀸을 놓기 시작하므로 오른쪽 위 대각선 방향, 윗 방향, 왼쪽 위 대각선 방향에 퀸이 있는지 탐색한다.

 

3.  모든 경로에 퀸이 없는 것이 확인되면 퀸을 놓고 다음 행으로 재귀 호출한다. (한 행 한 퀸)

 

4. 퀸을 N개 만큼 놓았으면 경우의 수 하나를 찾았기 때문에 answer++ 

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
int dire[2][3] = { {-1,-1,-1}, {0, 1, -1} };
int map[20][20];
int n, idx, answer, swi;

void search(int x, int y, int go)
{
	if (swi || x < 1 || x > n || y < 1 || y > n) return;
	if (map[x][y])
	{
		swi = 1;
		return;
	}

	return search(x + dire[0][go], y + dire[1][go], go);

}

void nQueen(int Queen, int x)
{
	if (Queen == n)// N개의 개수만큼 놓았으면 경우의 수 + 1
	{
		answer++;
		return;
	}

	for (int j = 1; j <= n; j++)
	{
		swi = 0;
		for (int k = 0; k < 3; k++) // 북서, 북, 북동 방향 체크
		{
			search(x + dire[0][k], j + dire[1][k], k);
			if (swi == 1) break; // swi가 켜지면 퀸을 놓을 수 없다는 뜻
		}

		if (!swi) // 모든 경로에 퀸이 없다면
		{
			map[x][j] = 1; // 퀸 표시
			nQueen(Queen + 1, x + 1); // 다음 행 재귀 호출
			map[x][j] = 0;
            // 현재 행에서 다른 열에 놓기위해 퀸을 지운다.
		}
	}
}

int main()
{
	scanf("%d", &n);
	nQueen(0,1);
	printf("%d", answer);
	return 0;
}