백준 9663 N-Queen c++ // 재귀, 백트래킹, 일반식도출, 백트래킹 시간복잡도

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

9663번: N-Queen

1. 일반식도출

1.1 / 대각선인경우 규칙 : (1,0) (0,1) -> x+y의 값이 1로 동일하다! -> (0,1)에 이미 두고 (1,0)에 두려고 할경우 isused[1]이 true이기 때문에 continue된다!

 

1.2 \ 대각선인경우 규칙 : (0,0) (1,1) -> x-y의 값이 0로 동일하다! -> (0,0)에 이미 두고 (1,1)에 두려고 할경우 isused[0]이 true이기 때문에 continue된다!

뺄셈의경우 -> 음수방지를 위해 n-1을 더해주면된다.

 

 

2.백트래킹 시간복잡도

백트래킹의 시간복잡도는 예상하기어렵다

-> 문제에서 N이 작을때 백트래킹을 시도한다.

-> N이 최대값일때 통과했으면 ok이다.

 

3. 전체코드

#include <bits/stdc++.h>
using namespace std;

int n,ret;
int isused1[40];	// | 에 퀸이있는지
int isused2[40];	// / 에 퀸이있는지
int isused3[40];	// \ 에 퀸이있는지

//cur번째 행(ㅡ)에 말을 놓는함수
void go(int cur) {
	if (cur == n) {
		//n번째 행에 퀸을 놓는데 성공한경우
		ret++;
		return;
	}

	//(cur, i)에 말을 놓는다.
	for (int i = 0; i < n; ++i) {
		if (isused1[i]) continue;	//같은 | 에는 둘수없다
		if (isused2[i+cur]) continue;	// / 에는 둘수없다
		if (isused3[i - cur + n - 1]) continue;// \ 에는 둘 수 없다.

		isused1[i] = 1;
		isused2[i+cur] = 1;
		isused3[i-cur+n-1] = 1;
		go(cur + 1);
		isused1[i] = 0;
		isused2[i + cur] = 0;
		isused3[i - cur + n - 1] = 0;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	go(0);
	cout << ret;
}