[문제풀이]백준 9633번: N-Queen

●해설

백트래킹을 사용하여 해결해야 하는 대표적인 문제이다.

 

 먼저 퀸이 같은 행 또는 열에 있으면 안되기 때문에 한 열당 하나의 퀸을 둔다는 것을 전제로 시작한다.

2차원 배열을 쓸 필요 없이 1차원 배열을 사용하여 배열의 index(i)를 열(raw)로, 배열의 값(arr[i])을 행(column)으로 잡는다.

int n;
int arr[MAX]; //arr[i]: column, i: row, arr[0]은 편의를 위해 쓰지 않음.
int cnt = 0; //경우의 수

 

 다음으로 퀸을 둘 자리가 다른 퀸의 공격범위에 있는지 체크를 해야한다.

같은 행에 있는 경우에는 간단하게 판별이 가능하다. 하지만 대각선에 있는 경우는 처음 보면 헷갈릴 수 있으니

잘 보고 이해해보자.

먼저 판별할 퀸의 좌표를(a, b)라고 하겠다. 그러면 좌표(a, b)의 대각선에 위치한 모든 좌표 (x, y)는

abs(x - a) == abs(y - b)를 만족한다(abs()는 절댓값). 아래 그림을 보고 잘 생각해보자. 

(대각선에 있는 모든 좌표에서 퀸의 좌표를 뺀 후 절댓값을 씌우면 위의 식을 만족한다.)

다음으로 판별식을 코드로 확인해 보겠다.

bool check(int v) { //1 ~ v - 1열에 있는 퀸의 공격범위에 있는지 체크
    for (int i = 1; i < v; i++) {
        if ( v - i == abs(arr[v] - arr[i]) || v == i || arr[i] == arr[v]) {
            return false;
        }
    }   
    return true;
}

열 v - 1까지의 모든 퀸의 좌표를 확인하기 위해 for문 사용하고, 각각의 열에 있는 퀸과 v에 놓일 퀸을 비교하여

놓을 수 없으면 false를 반환하도록 만들었다.

 

자 이제 판별식도 만들었으니 전체 코드를 확인해보자.

#include <iostream>
#define MAX 15
using namespace std;

int n;
int arr[MAX]; //arr[i]: column, i: row, arr[0]은 쓰지 않음(편의를 위해)
int cnt = 0; //경우의 수

bool check(int v) { //1 ~ v - 1열에 있는 퀸의 공격범위에 있는지 체크
    for (int i = 1; i < v; i++) {
        if ( v - i == abs(arr[v] - arr[i]) || v == i || arr[i] == arr[v]) {
            return false;
        }
    }   
    return true;
}

void BT(int v) {
    if (v == n + 1) { //n만큼의 퀸을 둔 것을 확인 했으니 cnt++
        cnt++;
        return;
    }
    for (int i = 1; i <= n; i++) { //1행부터 n행까지 차례대로 둠.
        arr[v] = i; //올려두고
        if (check(v)) {
            BT(v + 1); //가능하면 다음 열의 퀸으로 이동 
        }
    }
}
int main()
{
    cin >> n;
    BT(1);//1열부터 시작
    cout << cnt;
    return 0;
}

매개변수로 열의 index를 의미하는 v를 받고 for문으로 1부터 n행 까지 올려둘 수 있는지 판단한다.

둘 수 있으면 다음 열로 이동 후 이 과정을 v가 n과 같아졌을 때까지 반복 후 n + 1을 만나게 되면 경우의 수를 1 올려주고

return한다.