[백준] N-Queen

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

9663번: N-Queen

우선 문제부터 요약하면, NxN의 체스판에 Queen을 놓는 경우의 수를 구하는 문제입니다.

 

이전에 python으로 두 번 해결한 적이 있습니다. 

https://life318.tistory.com/91

[백준] N-Queen

https://life318.tistory.com/5

[프로그래머스] N-Queen

 

<Solution>

우선 모든 칸에 

1. Queen이 들어가거나 들어가지 않는 경우의 수 = 2^(NxN)

2. 각 행마다 Queen의 위치 선택 = N^N

이렇게 문제를 해결하게 되면, 시간복잡도가 많이 나오게 됩니다.

 

그래서 각 행과 열 모두에 Queen이 하나밖에 못오기 때문에, 매번 놓을 때 마다 해당 행과 열을 모두 경우의 수에서 없애는 방식으로 하면, N!의 시간복잡도로 문제를 해결 가능합니다. 

(사실 문제조건에서 가장 큰 값인 14를 잡으면, 14! ~= 870억 으로 이렇게 해도 큰 값이 나옵니다. 우선 이정도 값의 단순 연산은 10초안에 되나 봅니다) 

 

추가적으로, 매 행에 queen을 놓을 때 마다, 열, 대각선 양방향을 scan 하기 보다는 해당 부분에 queen을 놓을 수 있는지를 관리하는 array를 두면 O(1) 의 search time으로 빠르게 queen의 놓음이 가능한지를 확인 할 수 있습니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>

using namespace std;
int N;
int ans;

bool board[15][15];
bool colCheck[15];
bool crossCheck1[30];
bool crossCheck2[30];

bool available(int row, int col){
    return !(colCheck[col] || crossCheck1[row+col] || crossCheck2[col-row+(N-1)]);
}

void cal(int row){
    if(row == N){
        ans += 1;
        return;
    }
    for(int col= 0; col < N; col++){
        if(available(row, col)){
            board[row][col] = true;
            // col
            colCheck[col] = true;
            // cross 1
            crossCheck1[row+col] = true;
            // cross 2
            crossCheck2[col-row+(N-1)] = true;
            cal(row+1);
            board[row][col] = false;
            // col
            colCheck[col] = false;
            // cross 1
            crossCheck1[row+col] = false;
            // cross 2
            crossCheck2[col-row+(N-1)] = false;
        }
    }
}


int main(){
    cin >> N;
    cal(0);
    cout << ans << endl;
    return 0;
}