[백준] N-Queen 9663번

문제 링크

 

풀이

대표적인 백트래킹 문제라고 합니다. 백트래킹이란 깊이 우선 탐색 중에 오답을 만나면 이전 분기점으로 돌아가는 걸 말합니다. 재귀함수를 호출할 때 특정 조건일 때만 함수를 호출합니다. 트리로 봤을 때, 이전 분기점으로 돌아가 하위 노드가 구성되지 않은 모습을 가지치기라고도 합니다.

 

이 문제는 일차원 배열로 풀 수 있습니다. 문제를 보면 N x N 크기의 체스에 N개를 놓는 것이기 때문에 조건을 만족하는 경우의 수는 무조건 한 행에 하나의 퀸이 있어야 하기 때문에, 다음과 같이 표현할 수 있습니다.

rows[0] = 1 // 0번째 행의 1열에 퀸 놓기

 

퀸을 위치시키는 규칙을 말하기 전에 재귀함수의 탈출조건부터 살펴보겠습니다. 재귀함수는 반드시 탈출 조건이 있어야 하는데요. 그 탈출 조건이란 재귀함수가 N번째 행까지 도달했을 때입니다. 탈출 조건이면서 이 문제에서 구하고자 하는 경우의 수를 +1 하는 조건이기도 하죠.

 

퀸이 있을 수 있는 자리는 같은 행, 같은 열과 대각선 방향에 퀸이 없는 곳입니다. 재귀함수를 호출할 때 0번째 행의 어느열에 퀸을 놓았으면 다음 재귀함수는 1번째 행에서 위치를 찾을 것이기 때문에 같은 열에 있는지 여부와 대각선 방향만 고려하면 됩니다. 퀸의 위치를 좌표라고 생각하고 계산해보면 알겠지만 대각선 방향의 위치는 특정 위치 기준으로, 행과 열의 차이의 절대값이 같습니다.

 

예를 들어 (2,2)의 좌상->우하 방향의 대각선으로 한 칸 움직이면 (3,3)이며 우하->좌상 방향의 대각선으로 한 칸 움직이면 (1,1)입니다. 좌하->우상 방향으로 하면 (1, 3)이며 우상->좌하 방향으로 하면 (3,1)입니다. 즉 대각선 방향으로 한 칸 차이의 절대값이 1이며 두 칸 차이의 절대값이 2가 됩니다. 반복문은 내가 지금 놓고자 하는 위치의 행을 넘을 필요가 없습니다.

 

코드를 보면 경우의 수를 갱신하고 나서도 rows 배열을 초기화하지 않는 것은 어차피 1차원 배열이라서 매 수행할 때마다 배열이 새로운 값으로 갱신되며 갱신된 값만 가지고 가불을 판단하기 때문입니다.

 

코드

#include <cstdio>
int rows[15];
int answer;
int N;
/*
	rows[0] = 1 -> 0번째 행의 1열에 체스 놓기
*/
int abs(int a)
{
	return a < 0 ? -a : a;
}
bool test(int row)
{
	for (int i = 0; i < row; ++i)
		if (rows[i] == rows[row] || abs(rows[i] - rows[row]) == row - i)
			return false;
	return true;;
}
void n_queen(int row)
{
	if (N == row)
	{
		++answer;
		return;
	}
	for (int i = 0; i < N; ++i)
	{
		rows[row] = i;
		if (test(row))
			n_queen(row + 1);
	}
}

int main()
{
	scanf("%d", &N);
	n_queen(0);
	printf("%d\n", answer);
}