백준 9663 / N-Queen

어느 기업 입사 문제라던데, 생각해내기 너무 힘들어서 결국 답을 봐버렸다.

이 문제는 진짜 머리가 좋아야 풀 수 있는 거 같다.

n의 최대값이 15이기 때문에 최적화를 해야되는 문제.

아이디어는 이렇다.

모든 행과 열에 하나씩 놓여야하는 건 기본,

대각선이 문제인데,

대각선을 체크하는 배열을 1차원으로 선언해야한다.

  /의 경우, (row+col)의 값이 일정함을 이용.

        /(의 반대대각선)의 경우, (row-col+n)의 값을 일정함을 이용.

한 행마다 퀸을 하나씩 추가하는 방식으로, 추가하기전 체크를 해주고 추가하는 방식으로 풀 수 있다.

아마 시간초과 때문에 이렇게 최적화를 한것 같다. n이 작다면 그냥 2차원 bool 배열로 쉽게 풀 수 있다.

코드

#include<stdio.h>
#include<iostream>
 
using namespace std;
 
int n;
int ans = 0;
 
bool a[15][15];
 
bool check_col[15];
bool check_dig[40];
bool check_dig2[40];
 
 
bool check(int row, int col) {
 
    if (check_col[col])return false;
 
    if (check_dig[row + col])return false;
 
    if (check_dig2[row - col + n])return false;
 
    return true;
}
void calc(int row) {
 
    if (row == n) {
        ans++;
        return;
    }
 
    int cnt = 0;
 
    for(int col = 0; col < n; col++) {
        if (check(row, col)) {
            check_dig[row + col] = true;
            check_dig2[row - col + n] = true;
            check_col[col] = true;
            a[row][col] = true;
            
            calc(row + 1);
 
            check_dig[row + col] = false;
            check_dig2[row - col + n] = false;
            check_col[col] = false;
            a[row][col] = false;
 
 
        }
 
    }
    return;
}
int main() {
 
    cin >> n;
    
    calc(0);
    cout << ans;
}