JUNGOL/Intermediate_Coder/백트래킹-DFS/1889 : N Queen

Intermediate_Coder/백트래킹-DFS/N Queen

---

문제                                            

체스에서 queen의 가로, 세로, 대각선 방향으로 어느 곳이나 한 번에 움직일 수 있다.

즉 다음과 같은 체스판에서 queen이 X라고 표시된 위치에 있을 때, 

그 다음 queen이 움직여 갈수 있는 부분은 어둡게 칠해진 부분 중의 하나이다.

 

JUNGOL 백트래킹-DFS N Queen

 

N X N 크기의 정방형 체스판이 주어졌다.

우리는 거기에 N개의 queen을 배치하려고 하는데, 모든 queen들은 서로 잡아먹을 수 없어야 한다. 

그렇다면 queen들을 어떻게 배치해야만 할까? 

 

가능한 모든 경우의 개수를 출력한다.

 

입력 형식                                     

queen의 수 N(1≤N≤13)을 입력 받는다.

 

출력 형식                                     

N X N의 체스판에서 N개의 queen들이 서로 잡아먹지 않는 위치로 놓을 수 있는 방법의 수를 출력한다.

 

입력 예                                        

4

 

출력 예                                        

2

 

Hint!

N이 4일 때, 나오는 경우는 두 가지 이다.

JUNGOL 백트래킹-DFS N Queen Hint

---

NQueen.h

#include <iostream>
#include <algorithm>

#include "../../Base.h"

class NQueen : public Base
{
private:
	int GetNQueenCount(bool arr[][13], int n, int y = 0);
	void ColorQueenArea(bool arr[][13], int n, int x, int y);

protected:
	void Code() override;
};

 

NQueen.cpp

void NQueen::Code()
{
	int n;
	std::cin >> n;

	bool arr[13][13]{};

	std::cout << GetNQueenCount(arr, n);
}

/// <summary>
/// NQueen 이 가능한 경우의 수를 반환한다.
/// </summary>
/// <param name="arr">배열</param>
/// <param name="n">배열의 길이</param>
/// <param name="y">현재 진행할 y 좌표</param>
/// <returns>NQueen이 가능한 경우의 수</returns>
int NQueen::GetNQueenCount(bool arr[][13], int n, int y)
{
	if (y == n)
	{
		return 1;
	}

	int count{ 0 };
	for (int i = 0; i < n; i++)
	{
		// 퀸 영역인 경우 패스
		if (arr[y][i])
		{
			continue;
		}

		bool tempArr[13][13];
		for (int i = 0; i < n; i++)
		{
			std::copy_n(arr[i], n, tempArr[i]);
		}

		ColorQueenArea(tempArr, n, i, y);

		count += GetNQueenCount(tempArr, n, y + 1);
	}

	return count;
}

/// <summary>
/// 주어진 좌표에서 Queen 범위를 색칠한다.
/// </summary>
/// <param name="arr"></param>
/// <param name="n"></param>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
void NQueen::ColorQueenArea(bool arr[][13], int n, int x, int y)
{
	for (int i = 0; i < n; i++)
	{
		// 가로
		arr[y][i] = true;
		// 세로
		arr[i][x] = true;
		if (y - i >= 0)
		{
			// 좌상단
			if (x - i >= 0)
			{
				arr[y - i][x - i] = true;
			}
			// 우상단
			if (x + i < n)
			{
				arr[y - i][x + i] = true;
			}
		}
		if (y + i < n)
		{
			// 좌하단
			if (x - i >= 0)
			{
				arr[y + i][x - i] = true;
			}
			// 우하단
			if (x + i < n)
			{
				arr[y + i][x + i] = true;
			}
		}
	}
}

 

---

실행 결과 Success(100)

---

 

코드 해설

- 상태 공간 트리 개념 사용

상태 공간 트리는 결국 특정 상태를 저장하여 테스트하고 기존 상태로 돌아올 수 있는 것이라 생각했기에 재귀 함수 내부에서 이전 상태를 복사하고 새로운 상태를 만든 뒤 다음 재귀 함수로 넘기는 방식을 사용했다.

		bool tempArr[13][13];
		for (int i = 0; i < n; i++)
		{
			std::copy_n(arr[i], n, tempArr[i]);
		}

		ColorQueenArea(tempArr, n, i, y);

 

- 퀸 공격 범위 처리

퀸을 놓을 때 기존 퀸의 공격 범위에 존재하는 지를 매번 체크하는 대신 그 범위 자체를 놓을 수 없는 공간으로 지정하면 좌표가 주어질 때 해당 공간에 놓을 수 있는지만 체크하면 매번 체크하는 것보다 훨씬 빠른 처리가 가능하다.

void NQueen::ColorQueenArea(bool arr[][13], int n, int x, int y)
{
	for (int i = 0; i < n; i++)
	{
		// 가로
		arr[y][i] = true;
		// 세로
		arr[i][x] = true;
		if (y - i >= 0)
		{
			// 좌상단
			if (x - i >= 0)
			{
				arr[y - i][x - i] = true;
			}
			// 우상단
			if (x + i < n)
			{
				arr[y - i][x + i] = true;
			}
		}
		if (y + i < n)
		{
			// 좌하단
			if (x - i >= 0)
			{
				arr[y + i][x - i] = true;
			}
			// 우하단
			if (x + i < n)
			{
				arr[y + i][x + i] = true;
			}
		}
	}
}

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermediate_Coder/백트래킹-DFS/NQueen-JUNGOL