백준 9663번 N-Queen

 

문제는 여기

퀸은 배치된 칸을 기준으로 가로,세로, 그리고 대각선 이동이 가능한 가장 가치있는 말로 다음 빨간선과 같이 움직인다.

다음은 N이 8일때 해 중의 하나이다.

 

만약 모든 경우의 수에 대해서 재귀를 통해 브루트포스 방식으로 구한다음에 해인지 아닌지를 말단에서 체크하게 되면, DFS가 되는데, 

N=8인 경우 체스판의 칸 개수가 8x8=64개이고 이중에 8개를 고르는 조합의 수가 되므로 $_{64}C_8 = 4,426,165,368$이 되어 44억이 넘어갑니다. 이중에 92개만이 정답이죠.

가로로 겹치지 않게 한줄에 하나의 queen만 놓는식으로 가지치기(백트래킹)를 하게되면 $8^8 = 16,777,216$으로 줄어듭니다. (천6백만)

세로로도 겹치지 않게 permutation을 사용하는 백트래킹의 경우 $8! = 40,320$이 되어 훨씬 줄어듭니다.

다음과 같이 한줄씩 보면서 가로,세로,대각선 모두에 대해 백트래킹을 사용하면 5,508정도로 더 줄어듭니다.

이 문제의 경우 이정도 가지치기를 하면 제한시간내에 맞았습니다를 받을 수 있습니다.

 

 

소스코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
 
int N;
int vx[15+1], vy[15+1];
 
int go(int y, int x)
{
    //check valid (back tracking)
    for (int i = 0; i < y; i++) {
        if (y == vy[i] || x == vx[i]) return 0;  //직선겹침
        if (abs(x - vx[i]) == abs(y - vy[i])) return 0; //대각겹침
    }
 
    //terminal condition
    if (y == N - 1) return 1;
 
    //now record position
    vy[y] = y, vx[y] = x;
 
    //loop
    int r = 0;
    for (int i = 0; i < N; i++) {
        r += go(y + 1, i);
    }
 
    return r;
}
 
int main(void)
{
    scanf("%d", &N);
    int r = 0;
    for (int i = 0; i < N; i++) r += go(0, i);
    printf("%d\n", r);
    return 0;
}