N-Queen - 9663

문제 : https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

코드 : 

#include <iostream>
#include <vector>

using namespace std;

int N = 0;
int maxCount = 0;
int arr[4][2] = {
	{-1, -1},
	{-1, 1},
	{1, -1},
	{1, 1}
};
vector<std::pair<int, int>> temp;

bool AddCheck(int i, int j)
{
	for (auto v : temp)
	{
		// v.first == i 어차피 동일한 행이 들어올 수 없으므로 비교안해도 된다. 또한 대각선 구하는 공식 좀 알아두자... 
		if (v.first == i || v.second == j || abs(i - v.first) == abs(j - v.second))
		{
			return false;
		}
	}
	return true;
}

void solution(int i)
{
	//탈출조건
	if (i >= N)
	{
		if (temp.size() == N)
		{
			maxCount++;
		}
		return;
	}

	//다음조건
	for (int c = 0; c < N; c++)
	{
		if (AddCheck(i, c))
		{
			//저장
			temp.push_back(std::pair<int, int>(i, c));
			solution(i + 1);
			temp.pop_back();
		}

	}
}

int main()
{
	cin >> N;

	solution(0);
	cout << maxCount << endl;

	return 0;
}

이 문제의 키는 대각선 구하는 방식을 좀더 효율적으로 알고있으면 손쉽게 풀수있는 문제였다.

백트래킹 문제로 유명한 문제이다.

백트래킹이란 문제에서 주어진 모든 경우의 수를 다 계산하는 것이 아니라 계산하지 않아도 되는 것들은 탐색에서 제외하는 방식을 말한다. 

'시간초과' 를 방지하기위해서 꼭 필요한 개념이며, 반드시 숙지해야된다고 한다.

P.S 체스를 별로 안해봐서 퀸이 대각선으로 움직이는지 처음알았다... 그래서 당연히 상하좌우로만 움직이겠지 하고 계속 풀다가 답이 안맞아서 찾아보니 대각선으로도 움직였다는..