[알고리즘] N-Queen (백준, 9663)

문제

9663번: N-Queen

 

 

풀이

ruhz3/CodingTest

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

// ex) map[4] = 3 : 4열에 있는 퀸은 3행에 놓여 있습니다.
int map[15];
int N;

// 이 자리에 퀸을 놓아도 될지 검사
bool check(int idx, int n) {
	for (int i = 0; i < idx; i++) {
		// 행으로 겹칠 조건 || 대각선으로 겹칠 조건
		if (n == map[i] || abs(idx - i) == abs(map[i] - n))
			return false;
	}
	return true;
}

// 퀸을 열(idx) 별로 하나씩 배치
int setQueen(int idx) {
	// 모든 열에 채웠다면 1 반환
	if (idx == N)
		return 1;

	// 검사 후 다음 열 재귀호출
	int res = 0;
	for (int i = 0; i < N; i++) {
		if (check(idx, i)) {
			map[idx] = i;
			res += setQueen(idx + 1);
		}
	}
	return res;
}

int main() {
	cin >> N;
	memset(map, -1, sizeof(map));
	cout << setQueen(0) << endl;
	return 0;
}

먼저 경우를 완전히 재귀탐색할 수 있는지, 어떤 원리에 의해 경우를 줄일 수 있는지 따져보았다. 잠시 생각 끝에, 퀸을 놓을 수 없는 조건을 몇가지 찾아냈다

1. 퀸은 사방팔방으로 움직이기 때문에, 같은 행이나 같은 열에 하나 이상 있을 수 없다. 따라서 "map[열 번호] = 행 번호" 형식의 배열을 선언하고 열 번호를 0 → N까지 증가시키며 퀸을 놓기로 했다.​

2. 놓을 때 행과 대각선에 걸리지 않게 놓아야 했으므로, 이전 열들을 반복문으로 돌며 조건을 비교했다. 조건에 맞춰 재귀탐색 했고, 인덱스들이 조금 헷갈렸지만 짧은 코드로 구현할 수 있었다. 인덱스들의 뜻이 좀더 명확히 드러나도록 변수 이름을 정했다면 시간을 절약했을 것 같다.

​