2806. N-Queen - D3

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE

SW Expert Academy

N Queen은 정말 유명한 문제죠. 이 문제를 제가 한 4번 정도 풀어 본거 같은데, 풀 때마다 항상 헷갈리더라고요. 그래서 따로 정리를 해보고자 들고왔습니다.

---

모두가 잘 아시다시피 Queen의 경우 대각선과 같은 행, 열을 공격 가능합니다. N Queen 문제의 경우 이 공격 라인을 피해서 N개의 Queen을 놓을 수 있는 경우의 수를 따지는 문제입니다.

 

그렇다면 우선 한가지 짚고 넘어갈 수 있는 부분이 있습니다. 바로 한 행에는 하나의 Queen만 존재하고 한 줄에 하나씩 N개를 놓아야 한다는 점입니다. 즉, 행을 기준으로 삼는 일차원 배열을 만들어 낼 수 있습니다.

int arr[N] = { 0, };

 그럼 저기 일차원 배열엔 어떤 숫자가 들어가야 할까요? 바로 Queen이 놓이는 열을 채워 넣으면 됩니다. 아래와 같이 말이죠.

자, 그러면 저희는 다시 한 번 문제를 살펴볼 필요가 있습니다. 저희는 N개의 Queen을 놓을 수 있는 모든 경우의 수를 필요로 합니다. 그렇다는 말은 각 행 (arr[0], arr[1], arr[2], arr[3])에 대해서 반복문을 돌고, 단계를 높여가는 재귀적인 방식을 통해서 모든 경우의 수를 구해야하는 방법을 취해야 합니다.

거의 다 왔습니다. 이제 문제에서 제시한 Queen이 놓일 수 없는 경우를 처리만 한다면 코드를 짜도 될 것 같습니다.

빨간색 점이 정해졌다는 가정하에 두 파란 색 점은 Queen이 놓일 수 없는 위치입니다. 그 이유는 같은 열에 존재하고 대각선 위치에 존재하기 때문입니다.

 

왜 같은 행은 따지지 않느냐? 우리는 이미 depth라는 변수를 재귀적으로 넘기면서 행을 자연스럽게 처리를 해주었습니다. 그렇기에 열만 따졌으며, 빨간 점과 파란 x 표시를 가로, 세로 길이가 같은 곳들은 고려하지 않으면서 코드를 짠다면 문제를 해결할 수 있습니다.

 

그렇다면 N Queen 문제가 유명한 이유인 백트래킹 개념은 언제 나오는 걸까요?

 

사실 이미 우리는 백트래킹을 했습니다. 왜냐하면 전체를 탐색해서 그 중 정답인 답들을 고르는 게 아닌 중간에 Queen의 공격 범위를 제거했기 때문입니다. (바로 위 사진을 말합니다) 즉, 백트래킹이란 수학의 공식처럼 정해진 공식이 아닌 개념이라 아셨으면 합니다.

 

이제 코드를 살펴보도록 하겠습니다.

#include <stdio.h>
#include <malloc.h>

void NQueen(int* arr, int depth, int* result, int N);
int checking(int* arr, int depth, int n);
int abs(int num);

int main(void) {
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		int N, result = 0;
		scanf("%d", &N);
		int* arr = (int*)malloc(sizeof(int) * N);

		NQueen(arr, 0, &result, N);

		printf("#%d %d\n", t, result);
	}
}

void NQueen(int* arr, int depth, int* result, int N) {
	if (depth == N) {
		(*result)++;
		return;
	}
	else {
		for (int n = 0; n < N; n++) {
			if (checking(arr, depth, n)) { // 행(depth)과 열(n)에 놓일 수 있는지 없는지를 check
				arr[depth] = n;
				NQueen(arr, depth + 1, result, N);
			}
		}
	}
}

int checking(int* arr, int depth, int n) {
	for (int i = 0; i < depth; i++) { // arr에 이미 놓인 Queen들을 확인하기 위한 for문
    	// 같은 열에 존재하는지 혹은 가로 세로 길이가 똑같은지 확인
		if (arr[i] == n || abs(depth - i) == abs(arr[i] - n)) {
			return 0;
		}
	}
	return 1;
}

int abs(int num) {
	if (num < 0) {
		return -1 * num;
	}
	else return num;
}

NQueen은 문제를 해결하기 위한 재귀 함수이며, checking이라는 함수를 통해 Queen이 놓일 수 있는지, 없는지를 확인하고 놓을 수 있으면 depth를 증가시켜 (행을 증가시켜) depth가 N에 도달하면 경우의 수를 추가하는 방식으로 코드를 짜보았습니다.

 

또한, abs 함수는 가로 세로의 절대적인 길이를 비교하기 위해 사용했습니다.

---

이렇게 N Queen 문제를 풀어보았습니다. 항상 헷갈리던 문제를 이렇게 잘 해결하니 기분이 좋은데, 다음에 머리 초기화하고 다시 풀면 또 막힐거 같은 문제네요.

 

arr의 index는 행, value는 열 이 점만 잘 확인하고 문제를 푼다면, 언제든 쉽게 해결할 수 있을 문제인거 같습니다.

 

이상 2806. N-Queen - D3이었습니다. ^_^