[백준] 9663번 N-Queen

www.acmicpc.net/problem/9663

9663번: N-Queen

 

1793번 풀다가 세번째 풀어도 못푸는 나를 보고 자괴감에 빠져....

오늘은 이걸로 포스팅하기로 했다.

내일 아침 자력으로 풀어내면 1793을 내일 포스팅하겠다.

 

변수

isused1, isused2, isused3 - x = i 일때, 각각 체스판의 가로영역, 대각선영역, 반대대각선영역의 사용 여부를 나타냄

cnt - 퀸의 개수

n - 입력 값 N

 

알고리즘 방식

백트래킹을 통해 구현했다.

간단히 설명하면 cur = x 좌표, i = y좌표를 나타내며 백트래킹 방식을통해 탐색을 진행하고

if (cur == n)을 통해 조건을 충족하는지를 확인하여 결과값을 도출한다.

#include <iostream>

using namespace std;

int cnt = 0;
int n;
bool isused1[30];
bool isused2[30];
bool isused3[30];

void func(int cur) {
	if (cur == n) {
		cnt++;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (isused1[i] || isused2[i + cur] || isused3[i - cur + n - 1])
			continue;
		isused1[i] = 1;
		isused2[i + cur] = 1;
		isused3[i - cur + n - 1] = 1;
		func(cur + 1);
		isused1[i] = 0;
		isused2[i + cur] = 0;
		isused3[i - cur + n - 1] = 0;
	}
}


int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	cin >> n;
	func(0);
	cout << cnt;
}