[Baekjoon] 9663번: N-Queen

🥅 문제

https://www.acmicpc.net/problem/9663

 

🔍 설계

N-Queen에서 퀸들은 같은 행, 같은 열, 대각선에 놓이지 말아야 한다.

 

한 행씩 모든 열에 배치를 시도하고, 배치가 가능하면, 다음 행으로 넘어가서 배치한다. 이 과정을 반복한다.

 

check에서 현재 행과 현재 행 이전까지의 행을 살펴보기 때문에 같은 행에 놓일 수 없고, 같은 열인지, 대각선에 위치하는지만 확인하면 된다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int n, result = 0;
vector<int> col(15);

bool check(int cur_row) {
	for (int i = 1; i < cur_row; i++) {
		if (col[i] == col[cur_row]) {
			return false;
		}
		if (cur_row - i == abs(col[i] - col[cur_row])) {
			return false;
		}
	}
	return true;

}

void nqueen(int cur_row) {
	if (cur_row == n + 1) {
		result += 1;
		return;
	}

	for (int i = 1; i <= n; i++) {
		col[cur_row] = i;
		if (check(cur_row)) {
			nqueen(cur_row + 1);
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);	
	cin >> n;

	nqueen(1);

	cout << result << "\n";
	
	return 0;
}