Baekjoon 9663번 N-Queen

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n;
vector<int> q;

bool chk(int y, int x){
    for(int ry = 0; ry < n; ry++){
        if(q[ry] == -1) continue;
        if(q[ry] == x || abs(q[ry]-x) == abs(ry-y)) return false;
    }
    return true;
}

int bt(int y){
    if(y == n) return 1;
    int ret = 0;
    for(int x = 0; x < n; x++){
        if(chk(y, x)){
            q[y] = x;
            ret += bt(y+1);
            q[y] = -1;
        }
    }
    return ret;
}

int main(){
    fastio;
    cin >> n;
    q.resize(n, -1);
    cout << bt(0);
    return 0;
}

행을 기준으로 퀸을 놓을 자리를 하나만 고른다. 이는 같은 행에 다른 퀸이 놓이지 않는다는 것을 의미하기 때문에, 같은 열과 대각선 상에 다른 퀸이 존재하는지만 검사하면 된다. 놓여진 퀸의 좌표를 인덱스를 행, 값을 열로 하는 1차원 배열에 저장하여 관리하면 놓으려는 위치와의 좌표 계산으로 O(N) 시간만에 검사가 가능하다.