[알고리즘/문제풀이/BOJ 9663번] N-Queen

이 문제는 N*N 체스판에서 N개의 퀸을 놓을 수 있는 경우를 계산하는 아주 유명한 문제이다. 이 문제를 풀기 위해 N개의 퀸을 놓는 경우를 모두 조사하는 방식으로 진행하였고 따라서 백트래킹 기법을 사용하였다. 백트래킹은 트리 형태로 모든 경우를 탐색하는 기법이므로 재귀함수의 형태로 구현할 수 있고 재귀 함수의 탈출 조건에 문제에서 원하는 답을 얻기 위한 마지막 처리를 추가하는 식으로 코드를 작성할 수 있었습니다. 

N*N 체스판을 배열로 선언하여 직접 퀸을 체스판에 배치하고 퀸의 이동가능방향에 다른 퀸이 존재하는 지 확인하는 방식으로 문제를 해결할 수 있지만 이번에는 배열 사용을 줄이는 방향으로 코드를 작성해보았습니다.

가로, 세로, 대각선 방향으로 오직 1개의 퀸만이 놓일 수 있다는 사실에서 아이디어를 착안하여 가로, 세로, 대각선 2개의 점유 여부를 표현하는 배열을 선언하였습니다. 백트래킹 재귀함수에서는 가로 점유를 트리(재귀함수)의 높이(종료조건)로 사용하여 재쉬함수를 k개의 가로가 점유되어있을 때 N-k개의 퀸을 놓아 배치할 수 있는 경우의 수를 계산하는 함수로 정의하였습니다. 재귀함수를 거칠 때마다 가로 배열뿐만 아니라 세로와 대각선 배열 또한 갱신되므로 이 정보를 바탕으로 다음 랭크에서 퀸을 놓을 수 있는 위치가 가지치기되어 필요없는 연산을 최소화되도록 하였습니다. 원래는 재귀함수의 리턴 값으로 경우의 수가 출력되어야하며 그것이 함수의 정의와 이해에 편리하지만 구현상에서는 경우의 수를 전역변수로 선언하여 1씩 더하는 것이 편리하여 그렇게 구현하였습니다.

작성한 코드는 다음과 같습니다.

#include<stdio.h>

int N; //1<=N<15
long long int cnt = 0;

//모든 경우의 수를 탐색한다. - 백트래킹 기법 사용
//백트래킹 - 트리 구조로 모든 경우를 탐색 - 탐색 및 종료 기준이 될 depth가 중요
char rank[50], file[50], diagonal1[50], diagonal2[50];

void Nqueen(int RANK) {

	if (RANK == N) {
		cnt++; //경우의 수 1 증가
	}
	else {
		for (int i = 0; i < N; i++) {
			rank[RANK] = 1;
			if (file[i] == 1) continue;
			else {
				if (diagonal1[RANK + i] == 1) continue;
				else {
					if (diagonal2[RANK - i + N - 1] == 1) continue;
					else {
						file[i] = 1;
						diagonal1[RANK + i] = 1;
						diagonal2[RANK - i + N - 1] = 1;
						Nqueen(RANK + 1);
						file[i] = 0;
						diagonal1[RANK + i] = 0;
						diagonal2[RANK - i + N - 1] = 0;
					}
				}
			}
			rank[RANK] = 0;
		}
	}

}

int main(void) {

	scanf("%d", &N);

	Nqueen(0);

	printf("%lld\n", cnt);
	return 0;
}

30282705번 소스 코드 (acmicpc.net)