[Programmers] N-Queen

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen

n은 최대 12이기 때문에 모든 경우의 수에 대해 가지치기를 하며 진행하면 쉽게 풀 수 있는 문제였습니다.

똑같은 문제로 백준 9663번 N-Queen(https://jaimemin.tistory.com/813)이 있습니다.

백준 9663번 N-Queen

 

	#include <string>
	#include <vector>
	using namespace std;
	const int MAX = 12;
	int col[MAX + 1];
	int answer;
	bool promising(int idx)
	{
	int k = 1;
	bool flag = true;
	while (k < idx && flag)
	{
	if (col[idx] == col[k]
	|| abs(col[idx] - col[k]) == idx - k)
	{
	flag = false;
	}
	k++;
	}
	return flag;
	}
	void queens(int idx, int n)
	{
	if (promising(idx))
	{
	if (idx == n)
	{
	answer++;
	}
	else
	{
	for (int i = 1; i <= n; i++)
	{
	col[idx + 1] = i;
	queens(idx + 1, n);
	}
	}
	}
	}
	int solution(int n) {
	queens(0, n);
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~