N-Queen(백트래킹)

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

9663번: N-Queen

 재귀를 이용한 백트래킹 알고리즘 문제다.

 

 Queen은 행, 열, 대각선을 공격할 수 있으므로 새 Queen을 놓을때 기존의 Queen의 공격범위와 겹치지 않는지 판단해야 한다.

 

 행에 대해선 무조건 각자 다른 행에 놓도록 한다. i번째 퀸은 i행에 놓도록 함.

 이를 통해서 2차원 배열이 아닌 '열'의 정보값만 저장하는 1차원 배열을 사용하여 문제를 해결할 수 있다.

 

 열은 간단하게 배열의 앞부분을 탐색해주면 된다.

 

 대각선은 i행과 i-n행을 비교할때 n만큼의 거리차이가 나면 대각선 공격범위가 겹친다고 판단한다.

 

Q
		Q

 3번째 행의 Queen과 1번째 행의 Queen의 거리차이가 2(=3-1)만큼 차이나므로 대각선으로 겹친다.

 

Q
	Q

 

 3번째 행의 Queen과 1번째 행의 Queen의 거리차이가 1(!=3-1)만큼 차이나므로 대각선으로 겹치지 않는다.

 

 이러한 방법으로 Queen을 놓을때마다 기존에 놓인 Queen들 모두에 대해 겹치지 않는지 판단해준다.

 

 각 열의 Queen에 대해 다음 행의 Queen을 먼저 탐색하므로 DFS의 일종이라고 볼 수 있다.

 Queen을 놓을때 이전의 Queen과 겹치지 않을때만 다음 Queen으로 나아가게 하므로 가지치기를 통한 백트래킹을 사용한다고 볼 수 있다.

 

#include<iostream>
using namespace std;

int Queen[15] = { 0, };
int Size;
int ret = 0;

void QueenCheck(int n)
{
	for (int i = 1; i <= Size; i++)
	{
		Queen[n] = i;
		bool check = true;
		for (int j = 1; n - j >= 0; j++)
		{
			if (Queen[n] - Queen[n - j] == 0 || abs(Queen[n] - Queen[n - j]) == j)
			{
				check = false;
				break;
			}
		}
		if (check == true)
		{
			if (n + 1 == Size)
			{
				ret++;
			}
			else
			{
				// 재귀호출
				QueenCheck(n + 1);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> Size;

	QueenCheck(0);

	cout << ret << '\n';
}