백준 9663 N-Queen

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

9663번: N-Queen

처음 N-Queen 문제를 만나면 당황스럽습니다.

쉬워 보이는데 왜 풀면 내가 원하는대로 알고리즘이 안돌아가서 정말 정신에 해롭습니다.

 

백트래킹을 이용하면 쉬운문제라고 생각합니다.

그렇다고 단순히 백트래킹으로 한다면 백준 사이트에 N<15인경우 시간초과가 납니다.

 

처음에는 시간초과가 난다는것을 알았어도 단순하게 백트래킹으로 돌렸습니다.

소스는 아래와 같습니다.

#include<stdio.h>
int N;
int ret;
int map[16][16];
int dy[] = { -1,-1,-1,0,1,1,1,0 };
int dx[] = { -1,0,1,1,1,0,-1,-1 };
int chk[16];
 
void dfs(int y, int x, int idx)
{
 
    if (idx == N) {
        ret++;
        return;
    }
    for (int i = y; i < N; i++) {
        for (int j = x; j < N; j++) {
            if (map[i][j] == 0&&chk[i]==0) {
                if (i > 0 && chk[i - 1] != 1) return;
                int ny = 0, nx = 0;
                int flag = 0;
                for (int dir = 0; dir < 8; dir++) {
                    ny = i + dy[dir];
                    nx = j + dx[dir];
                    while (ny >= 0 &&ny <N && nx >=0 && nx < N) {
                        if (map[ny][nx] == 1) {
                            flag = 1;
                            break;
                        }
                        ny = ny + dy[dir];
                        nx = nx + dx[dir];
                    }
                    if (flag == 1)break;
                }
                if (flag == 0) {
                    chk[i] = 1;
                    map[i][j] = 1;
                    dfs(i + 1, 0, idx + 1);
                    map[i][j] = 0;
                    chk[i] = 0;
                }
            }
        }
        x = 0;
    }
}
int main(void)
{
    scanf_s("%d", &N);
    dfs(0, 0, 0);
    printf("%d", ret);
    return 0;
}
 

오랜만에 소스코딩을 해서 소스가 많이 더럽다. 하지만 12? 13입력은 나옵니다.

하지만 입력 14는 백년이 지나도 안나올것 같아서

다른 방식으로 알고리즘을 짰습니다.

 

3개의 체크 배열을 생성하는 방식으로 위의 시간초과를 해결했습니다.

행을 체크 하던지 열을 체크하던지 한곳만 잘체크 하면된다 배열 col 이 -> 행을 기준으로 체크를 대표합니다.

대각선 기준으로 체크는 배열 cross1 이 대표하고 수식으로 나타내면 cross1 에는 y+x로 배열에 0임을 확인

 

두번째 체크해야할 대각선은 배열 cross2가 대표하고 수식은 N+(y-x)로 배열이 0인것을 체크합니다.

이렇게 3개의 배열을

 

(!col[x] && !cross1[y + x] && !cross2[N + (y - x)])

 

(col[x] ==0 && cross1[y + x] ==0 && cross2[N + (y - x)]==0)  0인부분을 1로 바꾸어 체크하고

 

백트래킹으로 돌려 y가 N과 같다면 각 퀸들이 잘 들어가있다는것을 나타냅니다. 

 

아래 소스를 보고 직접 해보길 권합니다.

#include<stdio.h>
int col[14];
int cross1[26];
int cross2[26];
int N, ret = 0;
int n_Q(int y) {
    if (y == N) {
        ret++;
        return 0;
    }
    for (int x = 0; x < N; ++x) {
        if (!col[x] && !cross1[y + x] && !cross2[N + (y - x)])
        {
            col[x] = cross1[y + x] = cross2[N + (y - x)] = 1;
            n_Q(y + 1);
            col[x] = cross1[y + x] = cross2[N + (y - x)] = 0;
 
        }
    }
    return ret;
}
int main(void)
{
    scanf("%d", &N);
    printf("%d", n_Q(0));
    return 0;
}

 

맞았습니다!! 를 받을수 있습니다. 힘내봅시다.