[BOJ 9663] N-Queen

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

분류 : 백트래킹

 

N * N 체스판에 N개의 퀸을 놓는 경우의 수를 찾는 문제이다.

 

가장 빠른 방법은 미리 구해놓은 값을 리턴하는 경우이다.

N이 15 이하의 자연수 이므로 15개의 값만 미리 배열에 저장해 놓고 입력값에 따른 경우의 수를 리턴한다.

 

다음 그림은 n의 값에 따른 경우의 수의 개수이다.

예를 들어 N = 8일 경우, 8*8체스판에 8개의 퀸을 놓을 수 있는 경우의 수는 총 92가지가 된다.

 

가장 빠른 방법이긴 하지만, 알고리즘을 공부를 하는 입장에서는 도움이 되지 않는 방법이므로 백트래킹 방법으로 문제에 접근해보자

 

퀸 배치하기

우선, 퀸을 놓을 수 있는 상황에 대해 알아보자

 

퀸은 가로, 세로, 대각선 방향으로 이동이 가능 하므로, 퀸을 놓을 수 있는 경우는 다음과 같은 상황이다.

1. 같은 행에 다른 퀸이 없다.
2. 같은 열에 다른 퀸이 없다.
3. 대각선(오른쪽 아래로 향하는 대각선 ▧,  왼쪽 아래로 향하는 대각선 ▨) 방향에 다른 퀸이 없다.

 

8*8 체스판에 8개의 퀸을 놓는 8-Queen 방법을 통해 접근해보자

Step 1. 행과 열 겹치지 않게 체스판에 8개 배치하는 방법

64개 칸에 서로 다른 말을 배치하는 경우의 수는 다음과 같다. (nPr, 순열)

64 * 63 * 62 * 61 * 60 * 59 * 58 * 57 = 178,462,987,637,760

 

이 중에서, 행과 열이 겹치는 부분이 존재하므로 이부분을 제거할 수 있다.

행 또는 열에는 각각 1개의 퀸만 놓을 수 있으므로 다음과 같은 룰을 정할 수 있다.

• 각 행에는 1개의 퀸만 배치할 수 있다.
• 각 열에는 1개의 퀸만 배치할 수 있다.

 

우선, 각 행에 1개의 퀸만 배치할 수 있다고 해보자,

이 조건만으로 8의 8제곱(16,777,216)으로 줄어든다.

 

다음 그림은 각 행에 1개의 퀸만 배치할 수 있다고 가정했을 때를 나타낸다.

 

 

위 그림의 경우 열이 겹치는 경우 서로 공격할 수 있으므로,

각 행과 열에 1개의 퀸만 배치할 수 있다고 했을 때, 다음 그림과 같은 형태로 나타날 수 있다.

위와 같이 행과 열 두개의 조건이 추가될 경우, 8! = 40320 의 크기로 줄어든다.

 

구현 코드

#include<cstdio>

int N;

int cnt;
bool col[15];

void tracking(int r)
{
	if (r == N)
	{
		cnt++;
		return;
	}

	for (int c = 0; c < N; c++)
	{
		if (false == col[c])
		{
			col[c] = true;
			tracking(r + 1);
			col[c] = false;
		}
	}
}

int main()
{
	scanf("%d", &N);

	tracking(0);

	printf("%d", cnt);
}

 

위와 같이 구현하면 퀸(Queen)문제가 아닌 룩(Rook)문제를 푼 것이 된다. 따라서 대각선에 대한 처리도 해줘야 퀸에 대한 문제를 푸는 것이다.

Step 2. 대각선 겹치지 않게 체스판에 배치하기

(대각선에 대한 처리는 비숍 문제를 참고)

 

위 그림에서 다음과 같은 특징을 도출해 낼 수 있다.

1. ▧ 방향은 col - row의 값이 같다. (오른쪽 아래로 향하는 대각선)
2. ▨ 방향은 row + col의 값이 같다. (왼쪽 아래로 향하는 대각선)

위와 같이 계산하면 row col 두 값만 있으면 두개의 대각선을 모두 구할 수 있다.

이때, 주의 해야할 점은 ▧ 방향 계산은 음수가 나올 수 있다는 것이다. (row > col 인경우)

col - row의 최소값은 -(N-1) 이므로 col - row 값에 N-1(최대 인덱스 값)을 더해준 값을 취해서 계산한다.

=> col - row + N - 1

대각선의 총 갯수 : 2*N - 1개

 

구현 코드

#include<cstdio>

int N;

int cnt;
bool col[15]; // 해당 열에 퀸이 놓여져있는지 확인하기 위한 변수
bool diag[2][29]; // 두 대각선을 나타낸다. 크기는 r + c를 인덱스로 했을 때의 최대값으로 설정

void tracking(int r) // r : 행 번호이자, 현재 놓은 퀸의 개수를 의미한다.
{
	if (r == N) // 퀸을 모두 배치한 경우
	{
		cnt++;
		return;
	}

	for (int c = 0; c < N; c++)
	{
		/*
		r행 c열에 놓을 수 있는지 검사.
			1. c열에 퀸이 놓여져 있는지 확인
			2. 양쪽 대각선에 퀸이 놓여져 있는지 확인
		*/
		if (false == col[c] &&
			false == diag[0][r - c + N - 1] &&
			false == diag[1][r + c])
		{
			// 퀸을 놓을 경우, 행, 열, 대각선 체크를 한다.
			col[c] = diag[0][r - c + N - 1] = diag[1][r + c] = true;

			// r행 c열에 퀸을 놓았으므로, r+1행에 대해서 다시 조사한다.
			tracking(r + 1);

			// 현재 열(c)에 퀸을 놓지 않을 경우에 대해 생각한다. (이전 상태로 되돌림)
			col[c] = diag[0][r - c + N - 1] = diag[1][r + c] = false;
		}
	}
}

int main()
{
	scanf("%d", &N);

	// 현재 놓은 퀸의 개수가 0이고 0번째 행부터 시작
	tracking(0);

	printf("%d", cnt);
}