[BOJ / C++] N-Queen (백트래킹)

문제링크: https://www.acmicpc.net/problem/9663

 

1. 코드

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

void dfs(int x, int n, int& num, vector<bool>& isused0, vector<bool>& isused1, vector<bool>& isused2) {
    if (x == n) {
        num++;
        return;
    }

    for (int y = 0; y < n; y++) {
        if (isused0[y] || isused1[x+y] || isused2[n-1+x-y]) continue;

        isused0[y] = true;
        isused1[x+y] = true;
        isused2[n-1+x-y] = true;

        dfs(x+1, n, num, isused0, isused1, isused2);

        isused0[y] = false;
        isused1[x+y] = false;
        isused2[n-1+x-y] = false;
    }
}

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

    int n;
    cin >> n;

    vector<bool> isused0(n, false);
    vector<bool> isused1(2*n-1, false);
    vector<bool> isused2(2*n-1, false);

    int num = 0;
    dfs(0, n, num, isused0, isused1, isused2);

    cout << num;
}

 

 

2. 분석

isused0[y] 는 column이 겹치는지 판단한다. isused1[x+y] 는 우상에서 좌하로 떨어지는 대각선이 겹치는지 판단한다. isused2[n-1+x-y] 는 좌상에서 우하로 떨어지는 대각선이 겹치는지 판단한다. 각 대각선이 x+y, n-1+x-y가 일정하다는 것을 이용한 것이다. 각 대각선을 판단하는 배열의 크기는 2*n-1이다. x 축 행을 상태공간트리의 depth로 보고 y를 증가시키면서 각각을 판단해보면 된다.

 

 

3. 시간복잡도

첫 행에서 n개, 다음행에서 한개씩 배제되므로 n-1, n-2, ... ,1 이렇게 줄어들게 된다. 따라서 시간복잡도는 O(n!)이다.  이 문제의 시간제한은 10초이다. n은 최대 14이므로 14! = 87178291200 이고, 대략 9 * 10^10 정도 되고, pruning으로 실제는 더 줄어들게 되어 통과하게 된다.