[백준 9663] N-Queen (C++)

풀이

N X N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제다.

단순하게 생각하면 N^N^2(true, false) 모든 경우의 수를 비교해서 찾을 수 있지만, N의 크기가 커질수록 연산량이

감당할 수 없는 수준으로 된다. 따라서 가지치기(Pruning)를 하면서 문제를 해결해야 한다.

 

가치지기란?

어떤 강을 건너기 위해 돌다리를 두들겨보듯이 그 돌이 안전한지 안한지, 유망했는지 아닌지를 검사해서 유망하면 건너가고 아니라면 다시 돌아와서 다른 길을 선택하는 방법이다.

기존의 DFS처럼 주먹구구식으로 끝까지 가보는 것은 어떤 문제에서는 좋지만 이 문제에서는 연산량이 감당이 되지 않기 때문에 DFS처럼 탐색은 하지만 유망한 지 안 한 지를 검사해서 탐색의 범위를 좁혀가면서 문제를 해결한다.

 

N-Queen에서는 가지치기는 내가 어떠한 행(row)에 0 ~ N 중 하나의 열(col)에 Queen을 둔다고 가정했을 때,

다음 행(row + 1)에 Queen을 두기 전에 내가 두었던 Queen이 기존 [0 ~ row-1]까지 Queen들과 서로 공격하지 않는 범위에 두었는지를 체크하는 방법이다.

 

위에 그림처럼

row = 2인 행에 0번째 열에 Queen을 배치했다고 생각하자.

그러면 지금 둔 Queen이 적절한 배치인지를 확인하기 위해서 0번째 행에 배치한 Queen, 1번째 행에 배치한 Queen과의 충돌이 일어나지 않는지를 체크하면 된다.

 

체크할 때는 같은 행에 있는지 체크는 배제하면 된다. 이유는 해당 행에는 한 개의 Queen만 배치하기 때문이다.

체크하는 코드를 보자. 우리가 유망한지 체크하는 방법은 같은 열에 걸리거나 대각선에 걸리면 그것은 유망하지 않다.

이럴 경우에는 다시 해당 row에 Queen을 배치하지 않고 다른 열에다가 배치하고 유망한 지를 검사해보고,

만약에 유망하다면 row + 1에 Queen을 배치하러 가면 된다.

int col[15]; // col[i] = j : (i,j)에 Queen을 배치

bool isPromising(int row)
{
	// [0 ~ row) 단계 같은 열, 대각선 체크
	for (int i = 0; i < row; i++)
	{
		if (col[i] == col[row]) return false;
		if (abs(i - row) == abs(col[i] - col[row])) return false;
	}

	return true;
}

그렇다면 언제까지 Queen을 탐색할까?

row가 N까지 Queen을 잘 배치했다면, N x N 체스판 위에 N개의 Queen을 서로 공격할 수 없게 배치한 것이므로 이것은 문제에서 구하는 정답의 경우의 수 중 하나이기 때문에 개수를 하나 카운트하면 된다.

즉, row가 N이면 정답을 +1 증가시켜준다.

// row행 까지는 퀸을 놓은 상태,
void dfs(int row)
{
	if (row == n)
	{
		ans++;
		return;
	}
	// row행에 퀸을 배치하고 유망한지 체크
	// 유망하다면 다음 행에 퀸을 배치하러 가고,
	// 유망하지 않다면 다음 열에 다시 퀸을 배치하고 유망한지 검사한다.
	for (int i = 0; i < n; i++)
	{
		col[row] = i;
		if (isPromising(row))
			dfs(row + 1);
	}
}

 

정리하면,

각 단계(행)에서 어떤 열에 Queen을 둘지 정하고, Queen을 배치했다면 이전 단계에서 배치했던 모든 Queen들과 서로 공격하지 않는지를 검사해서 유망하다면 다음 단계로 넘어가고, 아니라면 그 단계에서 다음 열에 다시 Queen을 배치하는 방식으로 진행한다. 이렇게 하면 기존 DFS 탐색보다 빠르게 유망한 지 안 한 지 가지치기를 통해 더 빠르게 답을 구할 수 있을뿐더러 끝까지 탐색하지 않아도 된다는 장점이 있다.

 

전체 소스코드는 다음과 같다.

#include <iostream>
#include <cmath>
using namespace std;

int n, ans;
int col[15]; // col[i] = j : (i,j)에 Queen을 배치

bool isPromising(int row)
{
	// [0 ~ row) 단계 같은 열, 대각선 체크
	for (int i = 0; i < row; i++)
	{
		if (col[i] == col[row]) return false;
		if (abs(i - row) == abs(col[i] - col[row])) return false;
	}

	return true;
}

// row행 까지는 퀸을 놓은 상태,
void dfs(int row)
{
	if (row == n)
	{
		ans++;
		return;
	}
	// row행에 퀸을 배치하고 유망한지 체크
	// 유망하다면 다음 행에 퀸을 배치하러 가고,
	// 유망하지 않다면 다음 열에 다시 퀸을 배치하고 유망한지 검사한다.
	for (int i = 0; i < n; i++)
	{
		col[row] = i;
		if (isPromising(row))
			dfs(row + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	dfs(0);
	cout << ans << '\n';
	return 0;
}