BOJ 9663 N-Queen

www.acmicpc.net/problem/9663

9663번: N-Queen

사나이는 무릎꿇지 않는다. 잠들지 않는다. 임전무퇴 생즉사 쉐끼야. 뭐... 게임 트리를 C++로 구현하는 기분이라 오묘했다. 그 뭐였더라.. 어 디버깅은 어느정도 범위 넘어가면 프린트 해서 보자 라는 다짐을 또 가슴속에 새겼다. 근데 또 까먹겠지? 또 좀 막히면 에어에엉ㅇ 거리다가 F10이나 쳐 누르고 앉아있겠지? 그러지 말자 제발.

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<vector<int>> chessBoard;
long long ans = 0;
void simulate(int cnt){
	/*
	cout << "단 : "<<cnt << "\n\n";
	for (int x = 0; x < N ; x++) {
		for (int y = 0; y < N; y++) {
			cout << chessBoard[y][x] << " ";
		}
		cout << endl;
	}*/
	if (cnt == N-1) {
		for (int i = 0; i < N; i++) {
			if (chessBoard[i][cnt] == 0) ans++;
		}
		return;
	}
	for (int i = 0; i < N; i++) {
		if (chessBoard[i][cnt]==0) {
			chessBoard[i][cnt]++;
			for (int j = 1; j < N; j++) {
				//좌측 대각선 cnt = y i = x
				if (cnt+j < N && i-j>= 0) {
					chessBoard[i - j][cnt + j]++;
					
				}
				if (cnt + j < N) {
					chessBoard[i][cnt + j]++;
				}
				if (cnt + j < N && i + j < N) {
					chessBoard[i + j][cnt + j]++;
				}
			}
			simulate(cnt + 1);
			for (int j = 1; j < N; j++) {
				//좌측 대각선 cnt = y i = x
				if (cnt + j < N && i - j >= 0) {
					chessBoard[i - j][cnt + j]--;
				}
				if (cnt + j < N) {
					chessBoard[i][cnt + j]--;
				}
				if (cnt + j < N && i + j < N) {
					chessBoard[i + j][cnt + j]--;
				}
			}
			chessBoard[i][cnt]--;

		}
	}
}

int main() {
	ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	chessBoard = vector<vector<int>>(N);
	for (int i = 0; i < N; i++) {
		chessBoard[i] = vector<int>(N);
	}
	simulate(0);
	cout << ans;
	return 0;
}