백준 9663 N-Queen

예전부터 잘 안 풀렸던 문제인데 오랜만에 다시 시도해보니 통과했다.
어떻게하면 시간초과가 나지 않을까 고민을 했다.
편의상 행 = row, 열 = col, 오른쪽 대각선 = rdiag, 왼쪽 대각선 = ldiag라고 하겠다.
우선 row는 dfs 함수의 parameter로 관리를 해줬다. (같은 행에는 2개 이상의 퀸이 오지 못하기 때문)
오른쪽 대각선의 경우 차가 일정하므로 현재 좌표를 (x, y)라고 할 때, x - y로,
왼쪽 대각선의 경우 합이 일정하므로 x + y로 표현해주었다.
범위를 생각해보면,
열의 경우 0 ... n-1,
오른쪽 대각선의 경우 -(n-1) ... +(n-1),
왼쪽 대각선의 경우 0 ... 2(n-1)이 나온다.
열과 왼쪽 대각선의 경우는 배열의 인덱스로 표현할 수 있는 범위이지만 오른쪽 대각선의 음수 부분은 배열의 인덱스로 사용할 수 없기 때문에 n + 1을 더해줌으로써 이를 해결해주었다.

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

int n;
int col[14];
int rdiag[27]; 
int ldiag[27]; 
int cnt = 0;
void dfs(int row) {
    if (row == n) {
        // cases completed
        cnt++;
        return;
    }
    
    for (int i = 0; i < n; ++i) {
        if (col[i]) continue;
        if (rdiag[k-i+n-1]) continue;
        if (ldiag[k+i]) continue;
        col[i] = 1;
        rdiag[k-i+n-1] = 1;
        ldiag[k+i] = 1;
        dfs(k+1);
        col[i] = 0;
        rdiag[k-i+n-1] = 0;
        ldiag[k+i] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    dfs(0);
    cout << cnt;
}