[09663] N-Queen

[09663] N-Queen

문제

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

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

입력

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

출력

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

코드

#include <iostream>

using namespace std;

/* 조건 */
#define MAX 15

/* 변수 */
int N, ans = 0;
bool board[MAX][MAX]; // queen이 존재할 경우 true

/* 함수 */
bool isAvailable(int x, int y) {
    // 가로 세로 확인
    for(int i = 0; i < N; i++) {
        if(board[x][i] == true) return false; // x축으로 움직이므로 사실 필요 X
        if(board[i][y] == true) return false;
    }
    // 대각선 확인
    for(int i = 0, j; i < N; i++) {
        j = y - x + i;
        if(j >= 0 && j < N && board[i][j] == true) return false;
        j = y + x - i;
        if(j >= 0 && j < N && board[i][j] == true) return false;
    }
    return true;
}

void putQueen(int x, int y, int count) { // (x, y)에 넣음. count는 놓인 횟수
    if(isAvailable(x, y)) { // 놓을 수 있는 경우
        if(count == N) { // 모두 놓은 경우
            ans++;
            return;
        }
        board[x][y] = true; // queen을 놓고
        for(int i = 0; i < N; i++) // x + 1줄에 놓아봄
            putQueen(x+1, i, count+1);
        board[x][y] = false;
    } else return;

}

int main() {
    /* Fast cin cout */
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    /*****************/

    /* 입력 */
    cin >> N;

    for(int i = 0; i < MAX; i++) {
        for(int j = 0; j < MAX; j++) {
            board[i][j] = false;
        }
    }

    /* 풀이 */
    for(int i = 0; i < N; i ++) {
        putQueen(0, i, 1); // x = (0, i)에 '1번째'로 넣음
    }

    /* 출력 */
    cout << ans << '\n';
}

풀이

함수

• bool isAvailable(int x, int y)
  x, y좌표에 queen을 놓을 수 있는지 판별 후 true / false 반환
  가로 세로 및 대각선을 확인한다.
  이 풀이에서는 x좌표를 축으로 다음 queen을 놓기 때문에 세로로는 확인하지 않아도 되지만, 구현해 두었다. (이 부분만 삭제해도 전체 시간에서 1초정도 줄어든다.)
• void putQueen(int x, int y, int count)
  x, y에 queen을 놓아보는 함수이다.
  놓을 수 있는 경우 다음 x+1에서 하나씩 놓아보며 N까지 놓으면 방법의 수인 ans에 1을 더해준다.

풀이

board[x][y]는 (x, y)좌표에 queen을 놓았으면 true를, 빈 칸은 false를 저장하는 배열이다.
위 배열에 board[0][0]부터 board[N-1][0]까지 하나를 놓는 것으로 시작해 다음 줄에 하나씩 놓아보면서 가능한 경우를 탐색한다.
사용한 알고리즘(?)은 백트래킹 기법으로, N개를 놓을 때 까지 탐색한다.

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