[백준/C++] 9663 번 : N-Queen 풀이

백준 9663 번 : N-Queen

문제 링크 : www.acmicpc.net/problem/9663

9663번: N-Queen

---

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

---

체스에서 퀸은 같은 행, 열, 대각선 에 있으면 공격할 수 있다.

따라서 check(row, col) 에서는 같은 열, 같은 대각선 (/, \) 인지 꼼꼼하게 검사해야 한다.

(solve 에서 0행부터 차례대로 탐색하고 있으므로 행은 검사하지 않는다.)

 

1. 같은 열 검사 : col

check_col[40]

2. 같은 대각선 (/) 검사1 : row+col

check_dig1[40]

3. 같은 대각선(/) 검사2 : row+col+n-1

check_dig2[40]

검사 배열의 MAX 값이 40인 이유는 문제 조건에 있다.

n의 최대값이 14이므로 check_dig2 에서 최대값은 13+13+14 이기 때문이다.

 

check(row, col) 에서는 row 행 col 열에 퀸을 놓을 수 있을지 판별하고, 

solve(row) 에서 row행에 퀸을 몇 수를 놓을 수 있는지 계산한다.

 

전체 코드

#include <iostream>

using namespace std;

int n;
bool board[15][15];
bool check_col[40]; // | 열 검사 : col
bool check_dig1[40]; // / 대각선 검사 : row+col
bool check_dig2[40]; // \ 대각선 검사 : row+col+n-1

// row행 col열에 퀸을 놓을 수 있는지 판별
bool check(int row, int col){
    // | 열 검사
    if(check_col[col]) return false;
    
    // / 대각선 검사
    if(check_dig1[row+col]) return false;
    
    // \ 대각선 검사
    if(check_dig2[row-col+n-1]) return false;
    
    return true;
}


// row 행에 퀸을 어디에 놓을지 결정
int solve(int row){
    // n번째 행 도착 -> 모든 퀸 놓음 (cnt 증가)
    if(row>=n) return 1;
    
    int cnt = 0;
    for(int col=0; col<n; col++){
        if(check(row, col)){
            // 퀸 처리 (같은 열, 대각선 두 방향으로 못 놓게 처리)
            check_col[col] = true;
            check_dig1[row+col] = true;
            check_dig2[row-col+n-1] = true;
            
            // 퀸 놓음
            board[row][col] = true;
            cnt += solve(row+1);
            
            // 원래대로 되돌려놓음 (백트래킹)
            check_col[col] = false;
            check_dig1[row+col] = false;
            check_dig2[row-col+n-1] = false;
            board[row][col] = false;
        }
    }
    
    return cnt;
}

int main(void){
    
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    cout << solve(0) << '\n';
    
    return 0;
}

 

풀이 인증