[백준 9663번] N-Queen (C/C++)

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

9663번: N-Queen

---

본 포스트는 BaaakingDog님의 [바킹독의 실전 알고리즘] 0x0C강 - 백트래킹을 참고하여 작성하였습니다.

 

퀸의 움직임은 아래 이미지와 같습니다.

퀸의 움직임

처음엔 상태를 저장하는 2차원 배열을 사용해서 퀸이 이동할 수 있는 부분에는 true를 저장함으로써 백트래킹을 사용했습니다.

 

이 풀이의 경우 퀸을 놓는 순서까지 고려하기 때문에 factorial(n)으로 나눈 값을 출력하도록 했습니다. 

하지만, n의 최대 값은 15이고, factorial(15)의 값은 1307674368000으로 굉장히 많은 수의 경우의 수를 계산해야하기 때문에 백준 사이트에 제출시 시간 초과가 뜹니다.

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

bool used[15][15];
int num, n = 0;

void move(pair<int, int> pos){
    int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
    int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
    
    used[pos.x][pos.y] = true;
    for(int i = 0; i < 8; i++){
        for(int j = 1; j < n; j++){
            int nx = pos.x + (dx[i] * j);
            int ny = pos.y + (dy[i] * j);
            if(nx < 0 || ny < 0 || nx >= n || ny >= n) break;
            used[nx][ny] = true; 
        }
    }
}

void copy(bool from[][15], bool to[][15]){
    for(int i = 0 ; i < n; i++)
        for(int j = 0; j < n; j++)
            to[i][j] = from[i][j];
}

void queen(int q){
    if(q == 1){
        for(int i = 0; i < n; i++) 
            for(int j = 0; j < n; j++)
                if(used[i][j] == false) num++;
    }else{
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(!used[i][j]){
                    bool temp[15][15];
                    copy(used, temp);
                    move({i, j});  
                    queen(q - 1);
                    copy(temp, used); 
                }
            }
        }
    }
}

long long factorial(int n){
    if(n < 1) return 1;
    else return n * factorial(n-1);
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    queen(n);
    cout << num / factorial(n);
}

퀸의 움직임에 따르면, 행과 열에는 하나의 퀸만 놓을 수 있습니다. 또한 대각선 방향에도 하나의 퀸만 놓을 수 있습니다. 

따라서 열과 대각선에 대한 상태 정보를 저장하는 배열로 N-Queen 문제를 해결할 수 있습니다.

또한 이전 풀이와는 다르게, 퀸을 놓는 순서를 고려하지 않으므로, 계산량을 줄일 수 있습니다. 

#include <bits/stdc++.h>
using namespace std;

bool isused1[15];   // 열에 대한 상태 배열
bool isused2[40];   // 우상향 대각선에 대한 상태 배열
bool isused3[40];   // 좌상향 대각선에 대한 상태 배열

int n, ans = 0;

void queen(int r){  // 해당 함수는 (N-r) × N인 체스판 위에 r번째 행부터 
                    // 퀸 n - r개를 서로 공격할 수 없도록 놓는 경우의 수를 구하는 함수
    if(r == n){
        ans++;
    }else{
        for(int c = 0; c < n; c++){ // r은 행, c는 열
            if(!isused1[c] && !isused2[r + c] && !isused3[n - 1 + (r - c)]){
                isused1[c] = true;  // 열을 확인
                isused2[r + c] = true;  // 우상향 대각선을 확인
                isused3[n - 1 + (r - c)] = true;    // 좌상향 대각선을 확인
                queen(r + 1);
                isused1[c] = false;
                isused2[r + c] = false;
                isused3[n - 1 + (r - c)] = false; 
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    queen(0);
    cout << ans;
}