[BOJ] 9663 N Queen 알고리즘 - Back Tracking

NQueen 알고리즘은 Back Tracking 알고리즘의 대표적인 예이다.

간단하게 N개의 퀸을 크기가 N인 체스보드에 서로 공격할수 없게 배치 하려면 어떻게 해야 하느냐? 이다.

 

퀸의 경우 다음과 같은 공격범위를 가진다.

퀸의 공격범위.

따라서, 내가 N개의 Row를 탐색하려고 한다면, 이전에 어떠한 열에 두었는가?를

기억하면 그 다음 열에서는 탐색을 할 필요가 없다. (퀸이 Y축으로 쭉 공격이 가능한것임을 기억.)

예를 들어보자.

8A에 퀸을 두었다.

8A에 퀸을 두었으니 해당 Row 8은 더이상 둘수 없다. Col A 에도 더 이상 둘 수 없다.

이 정보를 기록해둔다.

헌데, 한 Row에 퀸을 두면 어짜피 다음 라인을 서치 할것이 아닌가? 

따라서 Col A에 퀸이 놓여있다는 것만 기억하면 된다.

 

Row를 8부터 1까지 돌면서 Back Tracking 하려한다.

그렇다면,

Row 8에서 A 두고 Branch 하는거다. 

Row 7 에서는 어디 둘지 고민중이다. 헌데 A에는 둘수 없다는 정보가 있으니 A에는 두지 않는다. 그래서 C에 뒀다.

Row 6 에서도 어딘가에 둔다. A와 C는 둘수 없는 정보가 있다.

Back Tracking 이 이렇게 동작한다. 재귀의 Depth를 이용해서 정보의 갱신과 초기화를 하고, Branch를 하는것이다.

 

이제 대각선에 대한 처리만 해주면 된다.

대각선 검사

체스판의 대각선을 구해보면 위 그림과 같이 나온다. 

우리는 대각선이 이전 시도에서 선점되었는지 알면 된다.

그래서 직선의 방정식을 구하고, 구한 방정식에 X와 Y를 대입했을때 Index가 나오도록 식을 구성한다.

코드를 구현 하면 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>

static constexpr int MaxSize = 15;

int Depth;
int	 Col                    [MaxSize]                   = { false ,};
bool DiagLine1              [2 * MaxSize - 1]           = { false, };
bool DiagLine2              [2 * MaxSize - 1]           = { false, };


int NQueen(int Y, int MaxDepth)
{
	if (MaxDepth == 1)  return 1;
	if (MaxDepth < 4)	return 0;
	if (Y == MaxDepth)	return 1;

	int Ret = 0;
	for (int X = 0; X < MaxDepth; ++X)
	{
		if (Col[X] == true || DiagLine1[Y + X] == true || DiagLine2[Y - X + MaxDepth - 1])
			continue;

		Col      [X]                    = true;
		DiagLine1[X + Y]                = true;
		DiagLine2[Y - X + MaxDepth - 1]	= true;
		Ret					+= NQueen(Y + 1, MaxDepth);

		Col      [X]                    = false;
		DiagLine1[X + Y]                = false;
		DiagLine2[Y - X + MaxDepth - 1]	= false;
	}
	
	return Ret;
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin >> Depth;

	std::cout << NQueen(0, Depth);
}