[PS] 백준 9663번: N-Queen

N-Queen

삼성 코테가 끝났으니 구현 말고 다른 유형도 풀어보고자
솔브닥 Class 4부터 뽀개보기로 했다.
이름이 행렬 제곱인 문제가 있길래 이 문제부터 해볼까 하다가,
살짝 감이 안잡혀서 일단 목록중에 보이던 N-Queen부터 처리했다...
내일은 저거 해버려야지...

근데 이게 시간이 1.8초밖에 안걸린다니 서버가 얼마나 좋은걸까?

 

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

#define pii pair<int, int>
#define endl "\n"
#define FOR(i, N) for (int i = 0; i < int(N); i++)
#define FORL(e, S) for (auto& e : S)
#define iib(r, c) (0 <= r && r < N && 0 <= c && c < N)

int N, ans = 0;

void back_track(int r, int c, int nqueen, int carr[15], bool to_bot[29], bool to_top[29]) {
	if (r >= N) return;
	if (nqueen >= N) { 
		ans += 1; 
		return; 
	}

	int nr = r + 1;
	FOR(i, N) {
		if (carr[i] == -1 && !to_bot[nr - i + N - 1] && !to_top[nr + i]) {
			carr[i] = nr; to_bot[nr - i + N - 1] = true; to_top[nr + i] = true;
			back_track(nr, i, nqueen + 1, carr, to_bot, to_top);
			carr[i] = -1; to_bot[nr - i + N - 1] = false; to_top[nr + i] = false;
		}
	}
}

int main() {
	cin >> N;
	int carr[15];		memset(carr, -1, sizeof(int) * 15);
	bool to_bot[29];	memset(to_bot, false, sizeof(bool) * 29);
	bool to_top[29];	memset(to_top, false, sizeof(bool) * 29);

	FOR(i, N) {
		carr[i] = 0; to_bot[0 - i + N - 1] = true; to_top[0 + i] = true;
		back_track(0, i, 1, carr, to_bot, to_top);
		carr[i] = -1; to_bot[0 - i + N - 1] = false; to_top[0 + i] = false;
	}

	cout << ans << endl;
	return 0;
}