/ ALGORITHM

Baekjoon 알고리즘 - 9663번 N-Queen c++

9663번 N-Queen

문제 접근 법

N * N 크기의 체스판에서 N개의 퀸을 체스판 위에 놓을 수 있는 경우의 수를 출력하는 문제이다.

N-Queen 문제는 백트래킹 기법을 사용하는 대표적인 문제이다.

이차원 배열을 사용해서 사용할 수 있지만, 1차원 배열을 사용하여 풀었다. 1차원 배열을 사용 할 수 있는 이유는 퀸을 자리에 놓을때 서로 다른 행을 놓는다고 전제하에 하기 때문에 가능하다. 다시 말해 1차원 배열의 인덱스는 행을 의미한다.

promising 함수에서 현재 놓여진 퀸이 제대로 된 자리에 있는지 확인을 한다. 같은 행에 위치해서는 안되고, 대각선에 위치해서 안된다.

nqueen 함수는 현재 놓여진 퀸들이 적절하다면 다음 퀸을 순서대로 위치 시켜 재귀함수를 부른다. 놓여진 퀸들이 적절하지 않으면 나를 부른 함수로 돌아가 퀸의 위치를 옮긴다.

#include <iostream>
#include <math.h>
using namespace std;
int n, answer = 0;
int map[16];

bool promising(int cnt) {
	bool flag = true;
	int i = 1;
	while (i < cnt && flag) {
		// 배열이 같은 값을 갖으면 같은 행임!!
		// 대각선에 위치해서는 안됨
		if (map[i] == map[cnt] || abs(map[i] - map[cnt]) == cnt - i) {
			flag = false;
		}
		i++;
	}

	return flag;
}

void nqueen(int cnt) {
	if (promising(cnt)) {
		if (cnt == n) {
			answer++;
			return;
		}
		else {
			for (int i = 1; i <= n; i++) {
				map[cnt + 1] = i;
				nqueen(cnt + 1);
			}
		}
	}
}

int main() {
	cin >> n;
	nqueen(0);
	cout << answer;
}