백준 9663번. N-Queen(c++) / 백트래킹

백트래킹 하면 가장 많이 떠올리는 문제이다.

근데 이 문제는 시간초과때문에 고생할 수가 있기 때문에 효율적인 최적화 작업을 해주어야 한다.

 

사실 글쓴이의 풀이보다 1차원 배열을 통해서 더 최적화해서 시간을 줄일 수 있는 풀이방법이 있는 것으로 알고 있다.

따라서, 코드는 참고만 해두시면 좋을 것 같다. (그닥 좋은 풀이는 아닌 것 같다... 시간이 오래 걸림;;)

 

아무래도 2차원 배열을 활용했고 더 가지치기를 할 수 있는데 적당히만 가지를 쳐서 시간이 오래걸리는 것 같다,,, 나중에 더 최적화를 해보는 걸로...

 

// N-Queen
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int n;
int ans = 0;
int chess[16][16] = { 0, };
int dx[3] = {-1, -1, -1};
int dy[3] = {0, -1, 1};
 
// 어차피, 같은 행과 그 뒤에 좌표들은 검사할 필요가 없기 때문에
// 위, 오르쪽 위 대각선, 왼쪽 위 대각선만 보면 된다.
bool check(int x, int y) {
    for (int i = 0; i < 3; i++) {
        int nx = x;
        int ny = y;
        while (1) {
            nx += dx[i];
            ny += dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                break;
            }
            if (chess[nx][ny] == 1) {
                return false;
            }
        }
    }
 
    return true;
}
 
void choose(int idx)
{
    if (idx == n) {
        ans++;
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if (chess[idx][i] == 0 && check(idx, i)) {
            chess[idx][i] = 1;
            choose(idx + 1);
            chess[idx][i] = 0;
        }
    }
}
 
int main()
{
    cin >> n;
    
    choose(0);
    
    cout << ans << "\n";
    return 0;
}