[SW Expert Academy] N-Queen

2806. N-Queen

SW Expert Academy의 문제는 무단 복제가 금지되어 있으므로 링크로 대체합니다.

N-Queen 문제는 대표적인 백트래킹 문제입니다!

마찬가지로 재귀 함수를 이용해서 풀 수 있습니다!

 

퀸의 특성상 한 행에 딱 하나의 퀸만 존재 할 수 있습니다!

때문에 총 N개의 퀸만이 존재할 수 있는 것이죠!

문제를 푸는 방법은 재귀 함수를 통해서 각 행마다 퀸을 놓을 수 있는 개수를 세서 반환하고 모두 더해주면 됩니다!

기저 사례는 맨 마지막에 퀸을 위치 시키려고 하는 경우이겠죠!

그리고, 놓인 퀸의 영향으로 놓지 못하는 곳을 항상 체크해 두는 것을 잊지 말아야 합니다.

하지만, 체크할 때에 유의해야할 것이 있습니다!

만약, bool을 이용해서 놓을 수 없다는 체크를 했을 때 생기는 문제죠!

그림으로 확인해 봅시다.

(2,3)의 퀸을 제거했는데, (1,1)의 퀸이 영향을 받아버렸습니다!

이를 해결하는 방법은 생각보다 간단합니다.

그냥 퀸을 놓을 때는 퀸이 1개 놓여있다. 라고 하고

퀸이 또 영향을 주면 퀸이 2개 겹쳐있다. 라고 하면 됩니다.

퀸의 영향력이 떨어지면, 1개를 빼면 되기 때문에 전에 겹쳐있던 퀸의 영역도 여전히 효력을 발휘할 수 있습니다!

깔끔합니다!!

코드

#include<cstdio>
 
int n, map[12][12];
 
int dx[3] = { -1,0,1 };
 
int nQueen(int depth)
{
    int res = 0;
 
    if (depth == n)
    {
        for (int i = 1; i <= n; i++)
        {
            res += map[depth][i] == 0;
        }
        return res;
    }
 
 
    for (int i = 1; i <= n; i++)
    {
        if (map[depth][i] == 0)
        {
            int cnt = 1;
            for (int j = depth + 1; j <= n; j++)
            {
                if (i - cnt > 0) map[j][i - cnt]++;
                if (i + cnt <= n) map[j][i + cnt]++;
                map[j][i]++;
                cnt++;
            }
 
            res += nQueen(depth + 1);
 
            cnt = 1;
            for (int j = depth + 1; j <= n; j++)
            {
                if (i - cnt > 0) map[j][i - cnt]--;
                if (i + cnt <= n) map[j][i + cnt]--;
                map[j][i]--;
                cnt++;
            }
        }
    }
 
    return res;
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++)
    {
        scanf("%d\n", &n);
        int res = nQueen(1);
        printf("#%d %d\n", tc, res);
    }
    return 0;
}