[백준 / C++] N-Queen(골드4, 9663)

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

문제

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

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

입력

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

출력

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

예제 입력 1

8

예제 출력 1

92

---

문제 풀이

이번 문제의 핵심은 실행 시간을 줄이는 것입니다.

 

저의 경우 처음에 N x N 크기의 2차원 배열을 만들어서 이중 for문(y, x)을 돌며 퀸을 놓을 수 있는 위치를 체크하는 방식으로 구현하였으나, 14를 테스트해본 결과 출력이 너무 느려서 로직을 바꿔야 겠다고 생각하게 되었습니다.

 

결국 N x N 크기의 배열에 N개의 퀸을 놓아야 하므로, 모든 y열과 x열에 하나씩 퀸이 존재해야 한다는 생각을 가지고 다음과 같이 1차원 배열로 방문 처리를 하게 되었습니다.

 

위 사진과 같이 x가 0, 1, 2, 3일 때 y값을 확인하는 방법으로 구현하게 되었습니다.

 

위와 같이 구조를 잡은 후 현재 위치에 넣을 y값이 이미 visited 배열에 있는지만 체크하면 퀸의 가로, 세로 이동에 대해 체크가 가능합니다.

 

대각선 판별은 현재 들어온 위치(x)와 for문을 순회하는 해당 위치(i)의 차의 절대값이 각각의 y값의 차의 절대값과 같은 경우 대각선에 위치해있다고 볼 수 있습니다.

 

예를 들어 (2, 3) 위치에 말이 들어올 수 있는지 체크한다고 가정한다면?

 

1. 현재 들어온 위치 x = 3, i번째 요소의 위치 = 1 이므로

| 3 - 1 | = 2가 되며,

 

2. 현재 들어온 위치의 y = 2, i번째 요소의 위치의 y = 0 이므로

| 2 - 0 | = 2가 됩니다.

 

즉,  1번과 2번이 같으므로, 대각선 위치에 있다는 것을 확인할 수 있습니다.

 

 

 

 

 

 

 

위와 같이 방문 처리를 빠르게 하기 위한 로직을 세우는 것이 어려웠던 문제였습니다.

코드

#include <iostream>
#include <string.h>
#include <vector>
#include <cmath>

using namespace std;

int n;
int res;

int visited[16];

bool Check(int cnt, int y)
{
	// 현재 칸이 -1인지 체크하기
	if (visited[cnt] != -1) return false;

	// visited 배열을 순회하며 들어올 수 있는 자리인지 체크
	for (int i = 0; i < n; i++)
	{
		// 만약 아직 비어있는 상황이라면 건너뛰기
		if (visited[i] == -1) continue;

		// 동일한 y값을 가진 요소가 있는지 체크
		if (visited[i] == y) return false;

		// cnt 칸의 y과 i 칸의 y값의 차를 계산합니다.
		// * cnt가 3이고 y가 1인 경우, i가 2인 위치에서는 y값이 0이나 1이 오면 안됩니다.
		// * 즉, |cnt - i| == | cnt칸의 y - i칸의 y|라면 대각선에 위치한 것입니다.
		if (abs(cnt - i) == abs(y - visited[i])) return false;
	}

	return true;
}

void Go(int cnt)
{
	if (cnt == n)
	{
		res++;
		return;
	}

	for (int i = 0; i < n; i++)
	{
		// cnt번째 위치에 i가 들어갈 수 있다면?
		if (Check(cnt, i))
		{
			// 방문 처리
			visited[cnt] = i;

			Go(cnt + 1);

			// 방문 해제
			visited[cnt] = -1;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	memset(visited, -1, sizeof(visited));

	Go(0);

	cout << res;
}