백준 9663번(Gold 4)

이번 포스팅은 9663번 Backtracking입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.https://www.acmicpc.net/problem/9663

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

#include <iostream>
#include <vector>

void Dfs(std::vector<int> &tmp, int idx);
bool promising(std::vector<int>& tmp, int idx);
int result = 0;
int main() {
	int N;
	std::cin >> N;
	std::vector<int> tmp(N, 0);
	Dfs(tmp, 0);
	std::cout << result;
	return 0;
}
bool promising(std::vector<int>& tmp, int idx) {
	for (int i = 0; i < idx; ++i) {
		if (tmp[i] == tmp[idx] || idx - i == abs(tmp[idx] - tmp[i]))
			return false;
	}
	return true;
}
void Dfs(std::vector<int> &tmp, int idx) {
	int N = tmp.size();
	if (idx == N) {
		result++;
		return;
	}
	for (int i = 0; i < N; ++i) {
		tmp[idx] = i;
		if (promising(tmp, idx)) {
			Dfs(tmp, idx + 1);
		}
	}
}