[성실코딩 6일차] 백준 #9663 N-Queen

N-Queens Problem 수업시간에 백트래킹으로 푸는거다 라고 배웠는데

막상 문제 풀려하니까 은근 생각해야되서 놀랫음

내가 안다고 생각하는거 = 모르는거

해본것 = 50%아는거

반복 학습 = !!!!!!

#include<iostream>

using namespace std;

int board[15][15] = {0,};
int n;
int cnt = 0;

int possibleR[15] = {0,};  // 행에 Queen이 있으면 
int possibleC[15] = { 0, };  
// 1열에 Queen이 있으면 1열에 퀸을 놓지 못함. possibleC[1]=1
// 1열에         없으면 1열에 퀸을 놓을 수 있음. possibleC[1]=0

bool checkPossible(int _r, int _c) {
	if (possibleR[_r]==1) { // 같은 행에 이미 queen이 있음
		return false;
	}
	if (possibleC[_c] == 1) {
		return false;
	}
	
	//대각선 아래오른쪽방향 검사하기
	int r = _r;
	int c = _c;
	while (1) {
		if ((r >= n || r<0) ||
			(c >= n || c<0)) { // 체스판 범위를 넘어갈 경구
			break;
		}
		if (board[r][c]==1) { // 퀸이 잇음
			return false;
		}
		r++;
		c++;
	}

	// 대각선 아래왼쪽방향 검사하기
	r = _r + 1;
	c = _c - 1;
	while (1) {
		if ((r >= n || r<0) ||
			(c >= n || c<0)) { // 체스판 범위를 넘어갈 경구
			break;
		}
		if (board[r][c] == 1) { // 퀸이 잇음
			return false;
		}
		r++;
		c--;
	}

	// 대각선 위오른쪽방향 검사하기
	r = _r - 1;
	c = _c + 1;
	while (1) {
		if ((r >= n || r<0) ||
			(c >= n || c<0)) { // 체스판 범위를 넘어갈 경구
			break;
		}
		if (board[r][c] == 1) { // 퀸이 잇음
			return false;
		}
		r--;
		c++;
	}

	// 대각선 위왼쪽방향 검사하기
	r = _r - 1;
	c = _c - 1;
	while (1) {
		if ((r >= n || r<0) ||
			(c >= n || c<0)) { // 체스판 범위를 넘어갈 경구
			break;
		}
		if (board[r][c] == 1) { // 퀸이 잇음
			return false;
		}
		r--;
		c--;
	}

	return true; // 가로,세로,대각선 모두 퀸없음
}

void nQueensProblem(int r) {

	if (r==n) { // 마지막 행까지 왔으니까 놓는 방법 성공!
		cnt++;
		return;
	}
	
	for (int j = 0; j < n; j++) {
		if (checkPossible(r,j)) { // board[r][j] 퀸을 놓을 수 있는지?
			board[r][j] = 1; // 퀸을 놓은 것을 표시
			// 표시 편하게 하기위해서 행,열도 표시
			possibleR[r] = 1;
			possibleC[j] = 1;
			nQueensProblem(r + 1); // 다음 행에 퀸 놓을 자리를 찾으러

			// 초기화
			board[r][j] = 0;
			possibleR[r] = 0;
			possibleC[j] = 0;
		}
	}
}

int main(void) {

	cin >> n;

	nQueensProblem(0);
	
	cout << cnt << endl;

	return 0;
}