[백준 9663] N-Queen

문제출처: https://www.acmicpc.net/problem/9663

구글에 백트래킹 검색해보시면 가장먼저 나오는게 n-queen 문제입니다.

기본적인 이해와 재귀호출을 정확히 이해해야하므로 학습하시고 올 것을 추천드립니다.

백트래킹의 대표적인 문제라서, 학습하시면 많은 소스코드들이있으니 풀이는 따로 적지않겠습니다.

코드

#include<iostream>
using namespace std;
int col[15];
int n, cnt;
void N_queen(int pos);
bool promising(int pos);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n;
	N_queen(0);
	cout << cnt << '\n';
}
void N_queen(int pos)
{
	if (pos == n)
		cnt += 1;
	else
	{
		for (int i = 0; i < n; i++)
		{
			col[pos] = i;
			if (promising(pos))
				N_queen(pos + 1);
		}
	}
}
bool promising(int pos)
{
	for (int i = 0; i < pos; i++)
	{
		if (col[pos] == col[i] || abs(col[i] - col[pos]) == pos - i)
			return false;
	}
	return true;
}

결과