[백준 9663] N-Queen

문제

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

 

해당 문제에 대한 풀이는 다음 블로그 글을 참고함

https://blog.encrypted.gg/945

[실전 알고리즘] 0x0C강 - 백트래킹

 

백트래킹과 브루트 포스를 이용하는 문제다.

코드

// 위아래, 대각선에 대해 isUsed 배열 3개를 사용
// isUsed_vertical: 같은 열에 퀸이 있는지 여부
// isUsed_leftDown_rightUp: 왼쪽 아래-오른쪽 위 대각선 상에 퀸이 있는지 여부
// isUsed_leftUp_rightDown: 왼쪽 위-오른쪽 아래 대각선 상에 퀸이 있는지 여부. 뒤에 붙는 (N - 1)은 인덱스 범위를 유지하기 위한 보정값

#include <bits/stdc++.h>
using namespace std;

int N;
int caseCount = 0;
bool isUsed_vertical[40];
bool isUsed_leftDown_rightUp[40];
bool isUsed_leftUp_rightDown[40];

// k번째 행에 말 배치하기
// (행, 열) -> (k, i)
void PlaceQueen(int k)
{
	if (k == N)
	{
		caseCount++;
		return;
	}

	for (int i = 0; i < N; i++)
	{
		if (isUsed_vertical[i] || isUsed_leftDown_rightUp[k + i] || isUsed_leftUp_rightDown[k - i + (N - 1)]) continue;

		isUsed_vertical[i] = true;
		isUsed_leftDown_rightUp[k + i] = true;
		isUsed_leftUp_rightDown[k - i + (N - 1)] = true;
		PlaceQueen(k + 1);
		isUsed_vertical[i] = false;
		isUsed_leftDown_rightUp[k + i] = false;
		isUsed_leftUp_rightDown[k - i + (N - 1)] = false;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;

	PlaceQueen(0);

	cout << caseCount;
}

아이디어

• 퀸은 상하좌우, 대각선 방향으로 움직일 수 있음 => 하나의 행에 하나의 퀸만 올 수 있다고 생각
• 행을 하나씩 내려가면서 퀸을 놓을 수 있는 경우 퀸을 놓으면 됨 (이렇게 하면 좌우 검사를 생략할 수 있음)
• 퀸을 놓을 수 있는 경우는 현재 위치에서부터 위, 오른쪽 위, 왼쪽 위 세 곳에 퀸이 없으면 됨

행 & 대각선 검사

열 검사

출처: https://blog.encrypted.gg/945

열 검사는 x 값이 같은 지 확인하면 된다.

왼쪽 아래 - 오른쪽 위 대각선 검사

출처: https://blog.encrypted.gg/945

 왼쪽 아래- 오른쪽 위 대각선 검사는 그 대각선 위에 있는 점의 x + y가 항상 같다는 성질을 사용하면 된다.

왼쪽 위 - 오른쪽 아래 대각선 검사

출처: https://blog.encrypted.gg/945

왼쪽 위 - 오른쪽 아래 대각선 검사는 그 대각선 위에 있는 점의 x - y가 항상 같다는 성질을 사용하면 된다.

이때, 인덱스가 음수가 되는 것을 방지하기 위해 보정값 n-1을 더해준다.

결과 저장

결과는 각각 bool형 배열 isUsed_vertical, isUsed_leftDown_rightUp, isUsed_leftUp_rightDown에 저장된다.

PlaceQueen 함수는 (k, i)에 퀸을 배치할 수 있는 경우를 확인하고, 가능하면 배치하는 함수다.

PlaceQueen 함수에서 세 가지 조건을 검사하기 위해 첨자로 들어가는 값은 다음과 같다.

• isUsed_vertical: i (x 값)
• isUsed_leftDown_rightUp: k + i (y + x 값)
• isUsed_leftUp_rightDown: k - i + (n - 1) (y - x 값 + 보정값 n-1)

세 가지 경우에 대해 모두 검사하면 세 배열에는 다음과 같은 값이 담기게 된다.

출처: https://blog.encrypted.gg/945

 

문제점 및 참고사항

• used 배열을 사용해 상하, 대각선을 O(1)로 검사할 수 있음
• 백트래킹 문제는 모든 경우를 확인하는 대신 N이 작은 경향이 있음