[백준 9663] N-Queen

유명한 nqueen 문제이다.

그냥 백트래킹으로 풀었는데 시간초과나서 틀뜰줄 알았던게 간신히 통과가 되었다

 

근데 이 풀이는 좋은 풀이가 아니다.

nqueen 중 시간이 넉넉한 문제를 풀어서 그렇지 

더 빠른 정해들이 있다.

 

더 빠른 정해는 마지막 코드임.

 

---

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int N;
int cnt;

void backtrack(int y, vector<pair<int, int>> queens) {

	if (y != queens.size()) return;

	if (y == N) {
		cnt++;
		return;
	}

	for (int x = 0; x < N; x++) {
		int flag = 1;
		// 배치 가능 검사
		for (int i = 0; i < queens.size(); i++) {
			int cury = queens[i].first;
			int curx = queens[i].second;

			// 같은 x좌표이거나 같은 기울기면
			if ((x == curx) || ((abs(y - cury) == abs(x - curx)))) {
				flag = 0;
				break;
			}
		}

		if (flag) {
			queens.push_back(make_pair(y, x));
			backtrack(y + 1, queens);
			queens.pop_back();
		}
	}
}

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

	cin >> N;

	vector<pair<int, int>> queens;
	backtrack(0, queens);

	cout << cnt;
	return 0;
}

 

이건 y=x+k y=-x-N+k 를 사용함

무조건 퀸은 기울기가 +-1인 대각선으로 움직일 수 있으니

해당 조건으로 풀이가 가능

 

#include <iostream>
#include <bitset>

using namespace std;

int N;
int cnt;

bitset<31> x;
bitset<31> positive_slope;
bitset<31> negative_slope;

void backtrack(int y) {
	if (y == N) {
		cnt++;
		return;
	}
	
	for (int curx = 0; curx < N; curx++) {
		if (!x[curx] && !positive_slope[curx + y] && !negative_slope[curx - y + N - 1]) {
			x[curx] = 1;
			positive_slope[curx + y] = 1;
			negative_slope[curx - y + N - 1] = 1;

			backtrack(y + 1);

			x[curx] = 0;
			positive_slope[curx + y] = 0;
			negative_slope[curx - y + N - 1] = 0;
		}
	}
}

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

	cin >> N;

	backtrack(0);

	cout << cnt;
	return 0;
}