[알고리즘 문제] 백준9663 - N-Queen

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

9663번: N-Queen

 

NxN판에 퀸을 놓을 수 있는 방법의 가지수를 구하는 문제 이다. 퀸을 놓을 수 있는 규칙은 자신의 대각선, 세로, 가로 방향에 다른 퀸을 놓을 수 없다는 점이다.

 

사실 N의 크기가 고정이라면 N중 for문으로 풀 수 있다. 하지만 N을 예측할 수 없기 때문에 재귀를 사용해야 한다. 

문제자체는 dfs로 풀어야 하며, 퀸을 놓을 수 있는 조건을 만족할 떄까지 계속 놓다가 마지막 레벨까지 갔다면 하나의 경우의 수를 찾은 것이다.

 

퀸의 위치는 check[]를 사용했는데 index는 행, check[index]는 열을 사용하였다. 예를 들어 [1,3,5]은 퀸의 위치가 1행1열, 2행3열, 3행5열에 위치함을 의미한다. 

 

여기서 중요한 점은, 퀸을 놓을수 있을지 없을지 검사하는 것인데 이는 isOverlap()가 검사한다. 이는 같은 열에 있는지와 같은 대각선상에 있는지 검사해야한다.

 

1. 같은 열에 있는지

check[]의 값이 열이라고 하였으니, 1 <= x  < level 인 범위에서 check[level]와 check[x]값이 같은지 다른지 검사한다. 같으면 같은열에 있는것으로 간주한다.

 

2. 같은 대각 선상에 있는지

두 점에서 대각선상에 있는지 여부를 검사하는 방법은 행의 길이와 열의 길이가 같은지 검사할 수 있다.

이는 level-x == math(check[level] - check[x]) 이면 같은 대각선상에 있음을 의미하는데 여기서 math인 경우는 음수값이 나올수 있기 때문이다. 

 

어쨋든 1,2 둘 중 하나라도 만족을 한다면 퀸을 놓을 수 없다는 의미가 된다.

 

#include <iostream>
#include <math.h>

using namespace std;

int check[16] = {0};
int result = 0;
int n;

bool isOverlap(int level)
{
    for (int i = 1; i < level; i++)
    {
        if ((check[i] == check[level]) || ((level - i) == abs(check[level] - check[i])))
        {
            return false;
        }
    }
    return true;
}
void dfs(int level)
{

    if (level == n + 1)
    {
        result++;
        return;
    }
    for (int i = 1; i <= n; i++) // 열
    {
        check[level] = i;
        if (isOverlap(level))
        {
            dfs(level + 1);
        }
    }
}

int main()
{

    cin >> n;
    dfs(1);
    cout << result;
}