[백준 9663번 C++풀이] N-Queen

걸린 시간 : NULL 

 

단계별로 풀어보기에서 만난 백트래킹 + 브루트포스 문제이다.

처음에는 체스판 하나하나 다 구현해야하는 줄 알고 4중 for문을 만들었지만 (ㅋㅋㅋ..) 만들면서 대각선 for문 처리할때

같은 대각선에는 x+y나 x-y가 같다는것이 성립하는 것을 알고, 좌측 상승 대각선의 체크리스트를 DLUP, 우측상승 체크리스트를 DRUP로 두고 y축을 t로 넘겨 t와 중복되는 줄, 대각선에 퀸이 있는지 판단후 놓는 식으로 퀸 처리를 마쳤다.

그리고 나올때는 다시 지워주는 식으로 백트래킹까지 구현하여 풀었다.

 

쉽지만 어려운 문제.

 

 

#include <iostream>
#include <set>
#include <vector>

using namespace std;
vector <vector <int>> chess;
vector <int> D1(15,0);
vector <int> DRUP(27,0);
vector <int> DLUP(27,0);
int N;
int cnt = 0;

void queen(int t)
{
	if (t == N)
	{
		cnt++;
		return;
	}
	else
	{
		for (int i = 0; i < N; i++)
		{
			if (D1[i] == 0 && DRUP[i + t] == 0 && DLUP[i - t + N - 1] ==0)
			{
				D1[i] += 1;
				DRUP[i+t] += 1;
				DLUP[i - t + N - 1] += 1;
				queen(t + 1);
				D1[i] -= 1;
				DRUP[i + t] -= 1;
				DLUP[i - t + N - 1] -= 1;


			}
		}
	}
	return;
}
int main()
{
	int M;
	cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		vector <int> tem(N, 0);
		chess.push_back(tem);
	}
	queen(0);
	cout << cnt;
}