BOJ 9663 - N-Queen 문제풀이

문제를 읽고 이해하기

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

재정의와 추상화

체스에서 퀸(Queen)은 본인이 있는 위치에서 대각선과 같은 행, 열에 있는 체스를 공격할 수 있다. 따라서 문제에서 말한 대로, 퀸이 서로를 공격할 수 없게 놓으려면 체스판 위에 놓인 모든 퀸이 서로를 공격할 수 없는 위치에 있어야 한다.

입력받은 N에 대하여, 행과 열은 각각 0 ~ N - 1 사이의 범위를 가진다고 하자. 이때 0번째 행부터 N - 1번째 행까지 순서대로 퀸 체스를 놓을 열의 위치를 부여하는 방식으로 알고리즘을 구성하자.

이 과정에서 isOkay 라는 이름의 함수를 만들어서 주어진 행과, 그 행에 부여할 열에 퀸을 놓을 경우 공격받을 수 있는지 확인하자. 다만, 우리는 0부터 N - 1번째 행까지 순서대로 열의 위치를 부여하므로, 주어진 행 이전의 행에 대해서만 확인해야 한다.

코드 작성

#include <iostream>
using namespace std;

int column[15] = { -1, };
int n;
int cnt = 0;

bool isOkay(int row, int col) {
    for (int i = 0; i < row; i++) {
        if (col == column[i]) // 다른 행에 내가 부여할 열이 부여되어 있는지 확인
            return false;
        if (abs(row - i) == abs(col - column[i])) // 대각선
            return false;
    }
    return true;
}

void dfs(int row) {
	// n번째 행까지 도달했을 경우
    if (row == n) {
        cnt++;
        return;
    }
    
    // row번째 행에 0 ~ n - 1까지의 열을 부여한다.
    for (int i = 0; i < n; i++) {
    	// 다만, row행 i열에서 공격받는다면 부여하지 않는다.
        if (!isOkay(row, i)) continue;
        // row행에 i열을 부여한다.
        column[row] = i;
        // row행에 i열을 부여한 상태에서 row + 1행에 대해 열을 부여하는 작업을 실시한다.
        dfs(row + 1);
        // row행에 부여했던 열을 제거한다.
        column[row] = -1;
    }
}


int main() {
    cin >> n;
    dfs(0);
    cout << cnt;

    return 0;
}