[Baekjoon] 9663번: N-Queen

 

 

 

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

9663번: N-Queen

 

---

 

문제 해결 과정

착안

백트래킹(backtracking, 퇴각검색) 알고리즘에 대한 대표적인 문제이나, 직접 풀어보는 건 처음이라 백트래킹이 아직 익숙하지 않아서 착안이 어려웠다. 생각해내기 가장 어려웠던 부분은 단계별로 배치되는 퀸에 의해 8 방향 직선으로 가려지는 체스판 상의 위치를 어떻게 표시해야 문제를 쉽게 해결할 지를 생각해내는 것이었다. 그래서 처음에는 체스판을 계속 새로 만들고 퀸의 위치마다 직선 방향으로 경로를 지워가며 비효율적으로 계산했었는데 이후 코드를 최적화하는 과정에서 보다 효율적으로 문제를 해결하기 위한 착안점을 도출해낼 수 있었다.

 

체스 게임에서의 퀸의 특성과 문제에서 주어진 조건으로부터 도출되는 핵심 착안점은 아래와 같다.

 

• $N \times N$ 크기의 체스판에 $N$ 개의 퀸을 올려놓으려면, 각 행에 반드시 하나를 올려야 한다.
• (위의 특징에 의해) 첫 번째 행부터 순차적으로 퀸을 배치한다면, 퀸의 경로 중 아래 방향의 경로만 확인하면 된다.
• bool 형이 아닌 정수형 배열로 체스판을 표현하여 단계별 퀸에 의해 가려지는 경로를 ++, 또는 -- 연산을 한다.

 

위의 착안점들을 활용해 문제를 보다 효율적으로 다시 해결할 수 있었다(자세한 설명은 아래 참고).

 

구현

첫 번째 착안점으로부터 맨 위의 행부터 순차적으로, 한 행에 하나씩 가능한 위치(열)에 퀸을 재귀적으로 배치하여 통해 문제를 해결하였다. 여기서 더욱 생각을 발전시키면 $N$ 번째 행에 $N$ 번째의 퀸이 놓여진다는 것까지도 확인할 수 있다(아래 코드에서 퀸이 놓인 개수인 placedQueens 변수가 체스판 위에서의 Y 좌표를 의미하는 부분에 해당).

 

이렇게 맨 위쪽 행부터 순차적으로 퀸을 배치하면, 퀸의 특성상 같은 줄에 2 개 이상의 퀸을 배치할 수 없으므로 반드시 다음 번째의 퀸은 현재 행보다 아래에 놓여야만 한다. 그러므로 퀸에 의해 가려지는 경로를 표시할 때는 해당 퀸의 위치보다 아래쪽인 행들에 대해서만 표시해도 된다. 따라서, $(x, y)$ 좌표에 놓여지는 퀸에 의해 체스판 상에서 가려지는 위치들을 표시하기 위한 함수인 SubordinatePaths() 함수를 구현할 때 퀸의 위치로부터 왼쪽/오른쪽 아래 대각선과 직선 아래 방향 위치들에 대해서만 표시를 하도록 구현하였다.

 

마지막으로는 체스판 상에서 퀸을 놓을 수 있는 여부를 정수형의 2차원 배열로 표현하면, 체스판을 나타내는 배열의 요소의 값을 1씩 증감하여 여러 퀸에 의해 중복되어 가려지는 경로를 표시할 수 있다. 따라서, 현재 단계에서 수정된 부분만 다시 이전 단계로 복구하는 것(trace back)이 용이해진다. 즉, 체스판 위의 특정 위치에 대한 요소의 값이 0인 경우는 퀸을 놓을 수 있는 위치임을 의미하고 SubordinatePaths() 함수에 의한 배열 요소 값의 변화는 아래와 같은 의미이다.

 

• 1 만큼 증가: 현재 단계에서 다음 번째의 퀸이 놓일 수 없도록 위치를 체크(중복 체크가 가능)하는 것을 의미.
• 1 만큼 감소: 현재 단계에서 체크한 과정을 다시 이전 단계로 복구하는 과정을 의미.

 

이를 활용하여 이전보다 효율적으로 문제를 해결할 수 있었다(SubordinatePaths() 함수의 세 번째 매개변수 관련).

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int N;
int Count;
int Placed[15][15];

void SubordinatePaths(int x, int y, bool bEliminate)
{
	int left = x, right = x;
	int sign = bEliminate ? 1 : -1;
	for (int i = y; i < N; i++)
	{
		Placed[i][x] += sign;
		if (--left >= 0) Placed[i][left] += sign;
		if (++right < N) Placed[i][right] += sign;
	}
}

void PlaceQueen(int X, int placedQueens)
{
	SubordinatePaths(X, placedQueens, true);

	if (placedQueens == N)
	{
		Count++;
		return;
	}

	for (int x = 0; x < N; x++)
		if (Placed[placedQueens][x] == 0)
			PlaceQueen(x, placedQueens + 1);
	
	SubordinatePaths(X, placedQueens, false);
}

int main()
{
	cin >> N;

	for (int x = 0; x < N; x++)
		PlaceQueen(x, 1);

	cout << Count << "\n";
	return 0;
}

 

실행 결과

 

가장 아래쪽의 결과는 처음 문제를 해결할 때, 비효율적으로 체스판을 반복해 그려나가며 문제를 해결한 결과이며, 가장 위쪽의 결과는 도출된 착안점들을 활용해 최적화를 한 결과이다.