BOJ 9663 : N-Queen

문제

---

문제 풀어보기

 

 

풀이

---

 

 

퀸을 먼저 배치하고 가능한 경우인지 판단하는 알고리즘을 하면

시간 초과로 문제를 풀 수 없었습니다.

 

 

그래서 다른 분의 블로그를 참조해서 백트래킹을 사용했습니다.

간단히 설명하자면

 

 

퀸을 하나 넣고 퀸의 이동반경을 모두 덱에 넣습니다.

퀸이 들어갈수 있는 곳에 넣으면서 계속 덱에 넣다 보면

퀸의 수가 N 개 이면서 덱의 사이즈가 N * N 이 되는 경우가 생깁니다.

바로 이경우가 퀸을 N 개 위치시킨 경우가 됩니다.

 

 

 

 

 

코드

---

#include <iostream>
#include <vector>
#include <deque>
#define safe(x,y) x>=0&&x<n&&y >=0&&y < n
using namespace std;

int dx[] = { 1,0,-1,0,1,1,-1,-1 };
int dy[] = { 0,1,0,-1,1,-1,-1,1 };
int n, ans;
bool check[16][16];

struct point {
	int x;
	int y;
};

deque<point> dq;

int move(int x, int y) {
	int q = 1;
	check[x][y] = true;
	dq.push_back({ x,y });
	for (int k = 0, nx, ny; k < 8; k++) {
		nx = x + dx[k];
		ny = y + dy[k];
		while (safe(nx, ny)) {
			if (!check[nx][ny]) {
				check[nx][ny] = true;
				q++;
				dq.push_back({ nx,ny });
			}
			nx += dx[k];
			ny += dy[k];
		}

	}
	return q;

}

void go(int index) {
	if (index == n) return;
	for (int i = 0, q; i < n; i++) {
		if (check[index][i]) continue;
		q = move(index, i);
		if (index == n - 1 && dq.size() == n * n) ans++;
		go(index + 1);

		while (q--) {

			auto cur = dq.back();
			dq.pop_back();
			check[cur.x][cur.y] = false;
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	go(0);
	cout << ans << endl;

	return 0;
}