(백준 9663번 N-Queen C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Backtracking 3

요즘 노코프님 유튭에 가입해서 보는 중인데, N Queens Problem을 쉽게 풀 수 있는 힌트가 담겨있어서 힌트를 사용해서 풀어보았다. 진짜 너무 감사한 분...🌟

 

시간이 된다면 저의 선생님께 구독과 좋아요 부탁드립니다..

(ㅋㅋㅋㅋ광고아님.. 모르는 분,,)

아마 유료 멤버십을 가입해야 볼 수 잇는 영상같다!!(12,000원에 엄청난 지식을 배울 수 있뜸!)

백준 9663번

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

9663번: N-Queen

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;

constexpr int MAX_N = 15;
int N;
int ans = 0;
int arr[15][15] = { 0 };
//D1 : -(N-1) <=x-y<= (N-1) >> 0<= x-y + (N-1) <= 2 * (N-1)
//D2 : 0 <= x+y <= 2 * (N-1)
int R[15] = { 0 }, C[15] = { 0 }, D1[30] = { 0 }, D2[30] = { 0 };



void BT(int row) {
	if (row == N) {
		ans++;
		return;
	}
	for (int col = 0; col < N; col++) {
		if (C[col] != -1 && D1[row - col + N - 1] != -1 && D2[row + col] != -1) {
			C[col] = -1;
			D1[row - col + N - 1] = -1;
			D2[row + col] = -1;

			BT(row + 1);

			C[col] = 0;
			D1[row - col + N - 1] = 0;
			D2[row + col] = 0;
		}
	}
}

int main() {
	scanf("%d", &N);
	BT(0);
	printf("%d", ans);
	return 0;
}

 

 

여기서 사용한 아이디어는 

하나의 말의 위치는 Row와 Column, 그리고 2개의 대각선 위치로 나타낼 수 있다는 점에서 착안한다.

 

빡구현하다가 눙물날뻔 했는데, 노코프님 유튭보고 15분만에 풀어버렸다 

캬캬