BOJ 9663 - N-Queen

문제

\(N \times N\) 크기의 타일에 \(N\)개의 퀸을 서로 공격하지 않게 배치할 수 있는 경우의 수를 구하는 문제이다.

\(1 \le N \le 15\)이다.

풀이

서로 공격하지 않으려면 각 행/열에 정확히 하나의 퀸만 존재해야 한다. 각 열마다 퀸의 존재유무를 기록하는 cstt 배열을 만든 뒤에 첫 행부터 퀸을 고정해가면서 경우의 수를 탐색했다.

solve(row, col)은 ar[row][col] 위치에 row+1 번째 퀸을 배치하는 것이다.
퀸을 배치한 후에는 cstt 배열을 확인해서 다음 행에 퀸을 배치할 수 있는 모든 경우의 수에 대해 재귀호출을 한다.

시간초과가 날 경우 자료구조를 벡터 -> 배열로 바꾸고 전역변수로 바꿔서 재귀호출을 최적화하는 방향으로 커팅해야 한다.

소스코드

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using lld = long long;

int ar[15][15];
int cstt[15];
int n;

int solve(int ni, int nj)
{
	int cnt = 0;
	if (ni + 1 == n)
		return 1;
	cstt[nj] = 1;
	ar[ni][nj] = ni;
	for (int i = 0; i < n; i++)
	{
		if (cstt[i] == 0)
		{
			int f = 0, nni = ni + 1, nnj = i;
			for (int j = -n; j < n; j++)
			{
				if (nni + j >= 0 && nni + j < n && nnj + j >= 0 && nnj + j < n && ar[nni + j][nnj + j] != -1)
					f = 1;
				if (nni - j >= 0 && nni - j < n && nnj + j >= 0 && nnj + j < n && ar[nni - j][nnj + j] != -1)
					f = 1;
				if (f == 1)
					break;
			}
			if (f == 0)
				cnt += solve(ni + 1, i);
		}
	}
	cstt[nj] = 0;
	ar[ni][nj] = -1;
	return cnt;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int cnt = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            ar[i][j] = -1;
        cstt[i] = 0;
    }
    for (int i = 0; i < n; i++)
      cnt += solve(0, i);
    cout << cnt;
    return 0;
}

풀고나서

• 유명한 문제라 당연히 점화식이 있을 줄 알았는데 너무 어려웠고, 알고리즘 분류를 보니 백트래킹이었다.
• 로컬에서 돌릴 때 14까지는 10초 이내로 돌아갔지만, 15에서는 최소 20초가 걸려서 커팅을 어떻게 더할지 고민하다가 일단 TLE 찍고 보자는 심정으로 돌렸는데 통과가 됐다.
• 다른 풀이들을 보니 모든 퀸들의 대각선 공격을 1차원 배열로 확인할 수 있었다.
  • 대각선의 기울기가 1으로 고정되어 있기 때문에, 임의의 퀸의 두 대각선의 수식은 각각 \(y=x+a\), \(y=-x+b\)이고, \(a\), \(b\) 만으로 같은 대각선에 속하는지 알 수 있다.
  • 따라서 임의의 퀸이 (i1, j1)에 위치해있다면, a[i1-j1], b[i1+j1]을 확인하는 것만으로 다른 퀸들과 대각선에서 만나는지 알 수 있다. 이때 i1-j1은 음수가 될 수 있기 때문에 n+i1-j1으로 처리해야 한다.
  • 이는 시간복잡도가 O(1)으로, 기존에 내가 확인하던 O(N)보다 훨씬 효율적이다. 내 풀이는 6000ms 정도가 나왔는데, 이 풀이를 적용한 다른 코드들을 확인해보면 1000ms 정도가 나온 것을 알 수 있었다.