백준 9663번 N-Queen

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

처음에 별생각없이 무식하게 2중for문 돌려서 구현했더니 답이 나오긴 나오는데 입력값이 10이 넘어가니까 시간이 너무 오래 걸렸다.

아니나 다를까 시간초과에 걸리고 결국 다른사람의 풀이를 보고 풀었다..

이 문제를 풀면서 문제 구상에 더 많은 시간을 써야 한다는것을 느꼈다.

직관적인 풀이법 보다 더 문제를 단순화하고 로직을 최소화하는 방법을 생각하는데 많은 시간을 들여야겠다고 생각했다.

아무튼 결국 풀이에 대한 접근은

1. N x N 칸에 N개의 퀸을 서로 공격할수 없게 놓아야 하므로 하나의 행에 하나의 퀸만 놓아야 한다

2. 퀸이 움직일수 있는 위치는 가로세로 대각선이다.

3. 행을 기준으로 퀸을 놓기때문에 내가 놓을 행에 퀸이 중복되는 경우는 없다.

퀸이 놓기 전엔 열과 대각선상에 퀸이 중복되는지만 확인해주면된다.

4. 열과 대각선상의 중복은 각각 배열 col, inc, decr에 저장하며 확인한다.

대각선상의 중복여부는 양의 기울기를 갖는 대각선의 x, y 좌표의 합이 일정하다는 사실과, 음의 기울기를 갖는 대각선의 x, y좌표의 차가 일정하다는 사실을 이용하였다.

코드는 아래와 같다

#include <iostream>
using namespace std;
 
int n, ans = 0;
bool col[14];
bool inc[27];
bool decr[27];
 
void recur(int r) {
    if (r >= n) {
        ans++;
        return;
    }
 
    for (int i = 0; i < n; i++) {
        if (col[i] || inc[r + i] || decr[n - (r - i) - 1]) continue;
        
        col[i] = inc[r + i] = decr[n - (r - i) - 1] = true;
        recur(r + 1);
        col[i] = inc[r + i] = decr[n - (r - i) - 1] = false;
 
    }
}
 
int main()
{
    cin >> n;
    recur(0);
    cout << ans << endl;
}