[백준][C++] 9663: N-Queen

문제 링크: https://www.acmicpc.net/problem/9663

 

8 queen problem! 정~말 유명한 백트래킹 문제죠. 백트래킹할 때 탐색 공간을 어떻게 줄일 것인지 예제로 보여주곤 하는 문제입니다.

탐색공간을 줄이는 과정을 한번 따라가봅시다. (출처: 강의자료)

• 체스판의 각 칸마다 1~64 번호를 붙이고 64칸짜리 bool 배열을 만든다
  --> 전체 탐색공간: 2^64 ≈ 1.84 * 10^19
• 체스판 각 칸마다 1~64 번호를 붙이고, 퀸 8개에 대해 몇번째 칸에 위치해있는지 저장하기 위해 8칸짜리 정수 배열을 만든다
  --> 전체 탐색공간: 64^8 ≈ 2.81 * 10^14
• 가지치기(Pruning)
  • ex) 위 방법에서 한 케이스를 중복되게 세는 경우를 막기 위해 퀸을 체스판 번호 오름차순으로 고른다
    --> 전체 탐색공간: 64 choose 8 = 4.426 * 10^9
• 한 행에 퀸이 하나밖에 올 수 없으니 퀸의 열만 저장하는 배열 8칸을 만든다
  • 8! = 40320
• 추가 최적화
  • 90, 180, 270도 돌렸을 때 중복되는 케이스를 거른다
  • 등등

 

뭐 어쨌거나 탐색공간을 잘 줄여야 합니다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;


int n;
ll counter;

void backtrack(vector<int>& queens, int current_row) {
	if (current_row == n) {
		++counter;
		return;
	}

	for (int i = 0; i < n; ++i) {
		bool ok = true;

		for (int j = 0; j < current_row && ok; ++j) {
			if (queens[j] == i || abs(queens[j] - i) == current_row - j)
				ok = false;
		}

		if (ok) {
			queens.push_back(i);
			backtrack(queens, current_row+1);
			queens.pop_back();
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> n;
	vector<int> q;
	backtrack(q, 0);
	
	cout << counter << '\n';

	return 0;
}

시간제한이 10초이기때문에 넉넉히 돌아갑니다. 한 5초 걸리네요. 퀸을 추가할 때 대각선과 열 체크를 하게 해놨습니다.

n=15부터는 수행시간이 훅훅 올라가기 때문에 10초로는 부족합니다. 딱 그 전까지, n=14까지만 입력이 주어지니까 시간 안에 돌아갑니다.

 

참고로 N퀸 문제의 수열은 OEIS A000170으로 등록돼있습니다