[백준] 9663번 N-Queen

1. 문제

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

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

상하좌우 대각선으로 이동이 가능한 퀸을 문제의 조건에 따라 놓는 경우의 수를 구하는 문제다. 입력으로는 N 이 주어진다. (1 ≤ N ≤ 15)

2. 풀이

체스판을 한 줄씩 검사해보며 체스판에 퀸을 넣는 경우의 수를 기록한다.

사실 풀이는 저게 끝이다. 한 줄씩 DFS로 체스판에 놓는 경우의 수를 기록해가며 총 몇 가지의 방법이 나오나 기록하면 된다.

하지만 바로 시간 초과가 뜨기 쉬운데, 이 문제에서의 핵심은 '검사를 어떻게 할 것이냐'에 있다.

결론적으로 검사를 하기 위해 N번 안에 다른 말들의 위치를 검사하고 놓을 수 있는지 판단을 하는게 중요했다.

이 풀이에서는 판에 놓을 말들을 저장하는 1차원 배열을 선언하고 인덱스 값은 X 값, 배열의 저장된 값을 Y 값으로 사용하여 판에 놓을 수 있는지 없는지 검사를 했다.

자세한 시행착오 과정은 후기에 적겠다.

3. 코드

#include <iostream>

using namespace std;

int N, Count;
int Queen[14];

void findQueen(int col)
{
	if (col >= N)
	{
		Count++;
		return;
	}

	for (int i = 0; i < N; ++i)
	{
		bool check = true;
		

		for (int j = 0; j < col; ++j)
		{
			Queen[col] = i;
			if (Queen[j] == Queen[col] || (col - j) == (Queen[col] - Queen[j]) || (col - j) == (Queen[j] - Queen[col]))
			{
				check = false;
				break;
			}
		}

		if (check)
		{
			findQueen(col + 1);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		Queen[0] = i;
		findQueen(1);
	}

	cout << Count;
}

4. 후기

시간 초과와의 싸움이었다.

처음에는 2차원 배열을 사용해서 퀸을 배치하고 검사를 진행하였는데 그렇게 되면 체스판을 순회하게 되므로 약 N^2의 시간복잡도가 나와 바로 얄짤없이 시간초과에 걸린다.

그래서 퀸은 상하좌우 대각선으로 움직이니 같은 행, 같은 열에는 배치를 못하는 것을 이용해서 1차원 배열로 만들었고, 검사를 진행할 때 배열 값을 가지고 비교를 진행했다.

대각선 검사는 똑같이 검사를 진행할 때 인덱스 값과 배열값을 가지고 간단한 계산을 거쳐 검사를 진행하니 1차원 배열을 한번 순회하는 것으로 모든 검사를 마칠 수 있게 되었다.

이번 문제는 N의 제한이 15로 되어있어 이 방법으로 풀 수 있었지만, 더 어려운 N-Queen 문제들은 어떤 방식으로 풀어야 할까 벌써 부터 궁금해진다.

+) 잡답으로 문제의 힌트에 Queen의 공연 영상이 있는데 그냥 문제 이름이라 올려놓은 것 같다ㅋㅋ