코딩하는 두꺼비

www.acmicpc.net/problem/9663

백트래킹의 대표적인 문제이다.

처음엔 2차원배열로 풀려고 했는데 결국 실패해서 힌트를 보고 풀 수 있었다. 어차피 하나의 열과 하나의 행에 하나의 퀸만 놓을 수 있기 떄문에 1차원 배열로 풀 수 있는 문제였다.

대각선 처리가 좀 까다로웠는데 각 행의 차이와 열의 차이가 동일하지 않는 다는 것을 아는 것이 포인트였다.

참고: chanhuiseok.github.io/posts/baek-1/

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int N, ans;
int map[16];

void dfs(int cnt) {
	int check = 0;
	if (cnt == N) {
		ans++;
		return;
	}
	for (int i = 0; i < N; i++) {
		map[cnt] = i;
		for (int j = 0; j < cnt; j++) {
			if (map[j] == map[cnt] || cnt - j == abs(map[cnt] - map[j])) {
				check = 1;
				break;
			}
		}
		if (check == 0) {
			dfs(cnt + 1);
		}
		else {
			check = 0;
		}
	}

}

int main() {
	cin >> N;
	dfs(0);
	cout << ans;
	return 0;
}