백준 알고리즘 9663번: N-Queen [C++]

문제 출처: www.acmicpc.net/problem/9663

9663번: N-Queen

1. 코드

#include <iostream>

using namespace std;

bool board[15][15];
int n, result = 0;

bool search(int x, int y)
{
	for (int i = 0; i < n; i++)
	{
		if (board[i][y]) return true; // 세로 열 체크

		// 왼쪽 (위) 오른쪽(아래) 대각선 체크
		if (x - i >= 0 && y - i >= 0 && board[x - i][y - i]) return true;	//2사분면

		// 왼쪽(아래) 오른쪽(위) 대각선 체크
		if (x - i >= 0  && y + i < n && board[x - i][y + i]) return true;	//1사분면
	}
	return false;
}

void solution(int p)
{
	if (p == n)
	{
		result++;
		return;
	}
	
	for (int y = 0; y < n; y++)
	{
		if (!board[p][y])
		{
			if (search(p, y)) continue;
			board[p][y] = true;

			solution(p + 1);
			board[p][y] = false;
		}
	}
}

int main(void)
{
	cin >> n;
	solution(0);
	cout << result;
	return 0;
}

(실행)

2. 풀이

참고 그림1

예시로 4를 입력받았을 때 위에 있는 참고 그림 1과 같이 크기로 2차원 배열을 생성하고 퀸의 위치를 논리 값으로 true로 나타낸다. 즉, 2차원 배열의 요소에 true값이 있다면 퀸이 있는 위치이고 그렇지 않고 false 값이 있다면 퀸은 현재 그 위치에 없는 것이다.

참고 그림2

만약 참고 그림 2와 같은 위치에 퀸이 있다고 한다면 다음 행으로 넘어 건너뛴다.

참고 그림3

그리고 주황색 위치에 퀸을 두려고 하는데 그전에 기존의 퀸과의 위치에서 서로 공격할 위치인지 확인을 한다.

참고 그림4

그래서 반복문과 조건문을 이용하여 주황색 퀸의 위치에서의 퀸의 공격 범위를 확인하고 다른 퀸의 위치와 겹치지 않으면 퀸을 둔다. 그리고 이 과정을 단순하게 반복해주면 된다. 그런데 이때 이 상태 그대로 반복을 해버리면 필요 없는 요소 또한 비교하게 되어 비교하는 경우를 조금 줄여보도록 하자.

참고 그림5

새로 놓을 퀸의 위치(주황색)를 기준으로 1 사분면과 2 사분면의 부분만 비교를 해주면 참고 그림 5와 같은 모양이 나와서 조금 더 효율적으로 비교할 수 있다. 그렇다면 어째서 3 사분면과 4 사분면은 비교를 안 하냐고 할 수 있는데 그 이유는 행을 기준으로 실행이 되기 때문이다. 퀸이 한번 놓이면 다음 행에서 다음 퀸이 놓일 위치를 찾기 때문에 3 사분면과 4 사분면에는 절대로 퀸이 있을 수 없다.  같은 이유로 가로 열 또한 확인하지 않는다. 그리고 이 과정을 반복하게 되면 원하는 답을 얻을 수 있다.

bool board[15][15];
int n, result = 0;

보드판을 만들기 위해 bool board [15][15]를 선언해주고 n은 사용자에게 입력을 받을 값이고 result는 n개의 퀸이 배치되었을 때 경우의 수를 확인하는 것이다.

int main(void)
{
	cin >> n;
	solution(0);
	cout << result;
	return 0;
}

먼저 사용자에게 n을 입력을 받고 solution 함수를 실행한 뒤 총경 우의 수인 result를 출력하면 끝이다.

void solution(int p)
{
	if (p == n)
	{
		result++;
		return;
	}
	
	for (int y = 0; y < n; y++)
	{
		if (!board[p][y])
		{
			if (search(p, y)) continue;
			board[p][y] = true;

			solution(p + 1);
			board[p][y] = false;
		}
	}
}

p는 퀸의 배치 수이고 그게 n과 같다면 result값을 증가시키고 함수를 종료한다. 그렇지 않다면 p행에서 반복문을 실행하여 search 함수가 true를 반환하면 continue를 하여 넘긴다. 그렇지 않다면 board에 퀸을 두고 재귀 함수를 호출한다. 그리고 재귀 함수에서 탈출하면 board의 값을 false로 초기화한다.

bool search(int x, int y)
{
	for (int i = 0; i < n; i++)
	{
		if (board[i][y]) return true; // 세로 열 체크

		// 왼쪽 (위) 오른쪽(아래) 대각선 체크
		if (x - i >= 0 && y - i >= 0 && board[x - i][y - i]) return true;	//2사분면

		// 왼쪽(아래) 오른쪽(위) 대각선 체크
		if (x - i >= 0  && y + i < n && board[x - i][y + i]) return true;	//1사분면
	}
	return false;
}

search 함수는 전달받은 x, y 값을 토대로 반복문을 실행하여 해당 위치에서 다른 퀸들을 공격할 수 있는지 확인한다. 세로 열과 X자인 대각선(1 사분면과 2 사분면) 또한 확인을 한 뒤 1개라도 있다면 true를 반환하여 참조하지 못하게 하는데 그렇지 않다면 false를 반환하여 해당 board의 위치에 퀸을 배치하게 한다.

3. 느낀 점

솔직히 문제는 간단할 거라고 생각을 했지만 처음부터 해결이 불가능한 방식으로 해결을 하려고 하다가 안 되는 걸 깨닫고 현재 이 방법으로 전환을 했는데 이 방법은 시간 초과가 상당하여 해결하는데 오랜 시간이 걸렸다. solution의 반복문에서 2중 반복문을 사용했었는데 그것이 문제가 되어 단일 반복문을 사용하여 해결하였다. 개인적으로 이 문제를 통해서 재귀 함수에 대해서는 조금 익숙해진 느낌이다.