[백준]9663N-Queen c++

1학년 때 수업 교재에 있었는데 못풀었던 기억이 있다. 이번엔 잘 풀려서 뿌듯했다.

n-queen은 가로,세로,대각선 방향 (2개) 에 하나의 퀸이 들어가야하는 문제이다.

가로,세로,대각선 두방향을 체크해줄 배열을 총 4개 만든다.

예를 들어 4 퀸이고  좌표가 2,3에 있다면 numX[2],numY[3],check[2+3],check2[4-1+2-3] 에 체크를 해주면 된다.

백트래킹을 통해서 경우의수를 세어주면 된다.

#include<iostream>

using namespace std;

int N;//N 1~14
bool numX[16],numY[16];  
int cnt;
int check[31],check2[31]; // 4퀸   /방향 대각선 x+y=0,1,2,3,4,5,6,7   \ 방향 대각 N-1 +x-y= 7,6

void NQueen(int y)
{

	if (y == N )
	{
		cnt++;
		return;
		
	}
	for (int i = 0; i < N; i++)
	{
		if (!numX[i] && !numY[y] && !check[i + y] && !check2[N-1 + i - y])
		{
			numX[i] = true; numY[y] = true; check[i + y] = true; check2[N-1 + i - y] = true;
			NQueen( y+1);
			numX[i] = false; numY[y] = false; check[i + y] = false; check2[N-1 + i - y] = false;

		}
		
	}
	
}

int main()
{
	//N 1~14
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;

	NQueen(0);
	cout << cnt;

}