BOJ 9663 - N QUEEN

저번에 마구잡이로 풀어봤지만 백트래킹 연습으로 한 번 더 풀어봤다.

 

1번줄부터 n번 줄까지 퀸을 배치하는데, x좌표가 중복되지 않게 뽑는 것을 백트래킹 해주면서 대각선에 다른 퀸이 배치돼있는지 검사해줬다.

 

#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>
using namespace std;

int n;

bool isValid(vector<int>& picked) { //대각선 검사만 해주면 된다. |(y'-y)| == |(x'-x)| 인경우 return false
	if (picked.empty()) return true;

	for (int i = 0; i < picked.size()-1; i++) { // {i, picked[i]} : 퀸의 위치 (y,x)
		for (int j = i + 1; j < picked.size(); j++) {
			if (abs(j - i) == abs(picked[j] - picked[i])) return false;
		}
	}
	return true;
}

int cnt = 0;
void go(vector<int>& picked, vector<bool>& isUsed, int k) {
    if (!isValid(picked)) return;
    
    if (k == n && isValid(picked)) {
		cnt++;
		return;
	}
	
	for (int i = 0; i < n; i++) {
		if (!isUsed[i]) {
	    	isUsed[i] = true;
	    	picked.push_back(i);
		    go(picked, isUsed, k + 1);
	    	picked.pop_back();
		    isUsed[i] = false;
        }
	}
}

int main() {
	scanf("%d", &n);
	vector<int> picked;
	vector<bool> isUsed(n, false);
	go(picked, isUsed, 0);
	printf("%d\n", cnt);
}

N과 M 문제를 풀 때 처럼 비슷한 논리로 재귀를 짜줬다.

 

8초조금 넘는 시간에 성공이 뜨는 거보니 더 초기화할 부분이 있을 것 같다.