[백준]9663_N-Queen

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

Solved

✔ 대표적인 백트래킹 문제
✔ 구조는 간단하다. n은 n*n 보드의 가로 또는 세로의 길이

void nqueen(int cnt) {
	if (cnt == n) answer++,return;
	int i = cnt + 1;
	for (int j = 1; j <= n; j++) {
    		if(visit[i][j]===true || able(i,j)==false) continue;
		visit[i][j] = true;
		nqueen(cnt + 1);
		visit[i][j] = false;
	}
}

using namespace std;
#include <iostream>

int n, answer;
int board[16][16],visit[16][16];

bool able(int x, int y) {
	int i, j;
	for (i = 1; i <= x; i++)//x축
		if (visit[i][y] == true) return false;
	for (i = 1; i <= y; i++)//y축
		if (visit[x][i] == true) return false;

	i = x - 1; j = y - 1;
	while (0 < i && 0 < j) {
		if (visit[i--][j--] == true) return false;
	}
	i = x - 1; j = y + 1;
	while (0 < i && j <= n) {
		if (visit[i--][j++] == true) return false;
	}

	return true;
}

void nqueen(int cnt) {
	if (cnt == n) {
		answer++;
		return;
	}
	int i = cnt + 1;
	for (int j = 1; j <= n; j++) {
		if(visit[i][j]===true || able(i,j)==false) continue;
		visit[i][j] = true;
		nqueen(cnt + 1);
		visit[i][j] = false;
	}
}
int main() {
	cin >> n;
	nqueen(0);
	cout << answer << '\n';
}