[SWEA] 2806. N-Queen

[URL]

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE&&&

SW Expert Academy

[풀이 과정]

​

1. DFS & 백트래킹 문제

2. 유망성 검토를 통하여 완전 탐색 중 백트래킹을 통하여 check하는 설정

3. 퀸 놓는 방법 map[][] == 0 인 경우 놓을 수 있다.

4. 퀸 하나를 놓을 경우 -> map[][]에 안되는 부분(가로, 세로, 대각선1, 대각선 2)을

plusOne()함수를 통해 1씩 증가

5. 백트래킹 - > 이전에 퀸을 놓으며 plusOne()함수를 통해 1씩 증가시켰던 부분을 되돌린다.

--> minusOne()함수를 통해 1씩 감소

6. 3번으로 되돌리며 퀸을 다 놓을때 까지 가능한 개수 계산

 

[소스 코드]

 

 

#include <stdio.h>
 
using namespace std;
 
const int MAX = 11;
 
int N;
int map[MAX][MAX];
int dap = 0;
 
void plusONE(int r, int c) {
    for (int i = 0; i < N; i++)        // 가로 1추가
    {
        map[r][i]++;
    }
 
    for (int i = 0; i < N; i++)        // 세로 1추가, (r,c) 제외
    {
        if (i == r)
            continue;
 
        map[i][c]++;
    }
 
    for (int i = 0; i < N; i++)        // 왼쪽 아래 오른쪽 위 대각선 1추가, (r,c) 제외
    {
        if (r - i >= 0 && c - i >= 0) {
            if (r-i == r && c -i == c)
                continue;
            
            map[r - i][c - i]++;
        }
 
        if (r + i < N && c + i < N)
        {
            if (r + i == r && c + i == c)
                continue;
            
            map[r + i][c + i]++;
        }
    }
 
    for (int i = 0; i < N; i++)        // 왼쪽 위 오른쪽 아래 대각선 1추가, (r,c) 제외
    {
        if (r - i >= 0 && c + i < N) {
            if (r-i == r && c -i == c)
                continue;
 
            map[r - i][c + i]++;
        }
 
        if (r + i < N && c - i >= 0)
        {
            if (r + i == r && c + i == c)
                continue;
 
            map[r + i][c - i]++;
        }
    }
}
 
void minusONE(int r, int c) {
    for (int i = 0; i < N; i++)        // 가로 1추가
    {
        map[r][i]--;
    }
 
    for (int i = 0; i < N; i++)        // 세로 1추가, (r,c) 제외
    {
        if (i == r)
            continue;
 
        map[i][c]--;
    }
 
    for (int i = 0; i < N; i++)        // 왼쪽 아래 오른쪽 위 대각선 1추가, (r,c) 제외
    {
        if (r - i >= 0 && c - i >= 0) {
            if (r - i == r && c - i == c)
                continue;
 
            map[r - i][c - i]--;
        }
 
        if (r + i < N && c + i < N)
        {
            if (r + i == r && c + i == c)
                continue;
 
            map[r + i][c + i]--;
        }
    }
 
    for (int i = 0; i < N; i++)        // 왼쪽 위 오른쪽 아래 대각선 1추가, (r,c) 제외
    {
        if (r - i >= 0 && c + i < N) {
            if (r - i == r && c - i == c)
                continue;
 
            map[r - i][c + i]--;
        }
 
        if (r + i < N && c - i >= 0)
        {
            if (r + i == r && c + i == c)
                continue;
 
            map[r + i][c - i]--;
        }
    }
}
 
void go(int cnt)
{
    if (cnt == N)
    {
        dap++;
        return ;
    }
    /////////////////////////////////////////////////////
    for (int j = 0; j < N; j++)
    {
        if (map[cnt][j] == 0)
        {
            plusONE(cnt, j);
            cnt++;
 
            go(cnt);
 
            cnt--;
            minusONE(cnt, j);
        }        
    }
}
 
int main()
{
    int T;
    scanf("%d", &T);
    for (int tc = 0; tc < T; tc++)
    {
        dap = 0;
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                map[i][j] = 0;
            }
        }
 
        go(0);
 
        printf("#%d %d\n", tc+1, dap);
    }
 
    return 0;
}