[BOJ] 9663_N-Queen with cpp

# 생각

시간초과에 유의해야 한다. N이 최대 14이기 때문에 14일 때 걸리는 시간을 확인해준다

퀸이 놓이는 자리의 열만 확인해주면 되기 때문에 2차원 배열은 필요없다

visited 배열을 활용하여 같은 열에 있는지, 좌측 우측 대각선 상에 있는지 체크를 해준다

* y 좌표가 같으면 같은 열에 위치

* x+y 좌표가 같으면 좌측 하단과 우측 상단을 잇는 대각선상에 위치

* x-y 좌표가 같으면 좌측 상단과 우측 하단을 잇는 대각선상에 위치

항상 확인 후에는 방문한 배열을 다시 false로 되돌려주는 것이 중요하다

 

 

# 전체 코드

// R : 10s, 128MB
// 1 <= N < 15
#include <bits/stdc++.h>
using namespace std;

int cnt = 0;
bool bUsed1[40];	// check column
bool bUsed2[40];	// check diagonal /
bool bUsed3[40];	// check diagonal \

void funcRecursive(int cur, int n)	// cur번째 row에 말 배치 예정
{
	if (cur == n)	// n개를 놓는데 성공했다면
	{
		cnt++;
		return;
	}

	for (int i = 0; i < n; i++)	// (cur, i)에 퀸을 놓을 예정
	{
		if (bUsed1[i] || bUsed2[i + cur] || bUsed3[cur - i + n - 1])
		{
			continue;
		}
		bUsed1[i] = true;
		bUsed2[i + cur] = true;
		bUsed3[cur - i + n - 1] = true;
		funcRecursive(cur + 1, n);
		bUsed1[i] = false;
		bUsed2[i + cur] = false;
		bUsed3[cur - i + n - 1] = false;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	cin >> N;
	funcRecursive(0, N);
	cout << cnt;
}

 

---

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

9663번: N-Queen