9663-N-Queen

www.acmicpc.net/problem/9663

9663번: N-Queen

본 문제는 브루트포스 알고리즘을 사용하여 풀었습니다. 그런데 모든 경우를 일일히 탐색하는 것은 불가능합니다. NxN 체스판에 퀸 N 개를 놓을 수 있는 경우의 수는 \({{}_{N^2}\mathrm{C}_{N}}\) 이며 N = 15 일때, 91,005,567,811,177,478,095,440 가지의 경우를 고려해야합니다. 그렇기 때문에 우리는 퀸을 놓으며 걸러낼 수 있는 경우의 수는 최대한 걸러내야 합니다.

 

먼저, 문제 및 체스의 규칙상 퀸은 서로 같은 행과 열에 놓이면 안됩니다. 즉, NxN 체스판에 N 개의 퀸을 규칙에 맞게 놓기 위한 충분조건으로 각 행과 열에 반드시 한개의 퀸만 놓아야 합니다. 코드로 구현할때에도 이 점을 고려하여 체스판의 행 혹은 열 중 한 축을 기준으로 삼으면 1차원으로 배열로 퀸의 위치를 표현할 수 있습니다.

 

위 조건을 잘 생각하여 체스판의 행 혹은 열 중에서 한 축을 기준으로 삼아봅시다. 행을 기준으로 삼으면 첫 번째 행에서 N 개의 열 중 하나의 열에 퀸을 놓게되면 첫번째 행에는 더이상 퀸을 놓지 못합니다. 즉, 바로 다음 행에서 퀸을 어디다 놓을지 고려해주면 됩니다. 여기서, 추가적으로 이전 행에 놓았던 퀸이 위치하는 열은 퀸을 놓지 못합니다. 이를 고려하면 N! 가지의 경우를 탐색하면 됩니다. 하지만, N 이 15일때, 여전히 15! = 1,307,674,368,000 가지의 경우를 탐색해야 하기때문에 무리가 있어보입니다. 

 

 

여기에! 추가적으로 대각선상에 놓인 경우를 탐색하고 이를 생략하면 보다 적은 경우를 탐색하여 답을 구할 수 있습니다. 두 퀸의 위치를 칸이 놓인 행, 열로 표현하였을때, 두 퀸간의 행과 열의 Manhattan Distance 가 서로 같다면 대각선상에 놓인 것으로 판단할 수 있습니다.

코드

#include <iostream>

using namespace std;

int N;
int map[15] = {0, }; //map[i] = j, 체스판의 i 번째 행에 j열에 말이 놓여있다. 말이 안놓인 경우 -1
bool visited_col[15] ={false, };

int answer = 0;

bool overlap_check(int cur_row, int cur_col)
{
    bool overlapped = false;
    
    for(int row = 1; row < cur_row; row++)
    {
        if(map[row] != -1) // 대각선에 말이 존재하는 경우
        {
            int drow = abs(row-cur_row);
            int dcol = abs(map[row]-cur_col);
            if(drow == dcol)
            {
                overlapped = true;
                break;
            }
        }
    }
    
    return overlapped;
}

void dfs(int row)
{
    if(row == N + 1)
    {
        answer += 1;
        return;
    }

    for(int col = 1; col <= N; col++)
    {
        if(visited_col[col] == false and overlap_check(row, col) == false)
        {
            map[row] = col;
            visited_col[col] = true;
            dfs(row + 1);
            map[row] = -1;
            visited_col[col] = false;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for(int i = 0; i <= 14; i++) 
    {
        map[i] = -1;
        visited_col[i] = false;
    }
    //freopen("9663.txt", "r", stdin);
    cin >> N;

    for(int i = 1; i <= N; i++)
    {
        map[1] = i; // 1 번째 row 에 i번째 행에 말을 놓겠다.
        visited_col[i] = true;
        dfs(2);
        map[1] = -1;
        visited_col[i] = false;
    }

    cout << answer;
}