[알고리즘] N-Queen

백트래킹(BackTracking)

가능한 모든 방법을 탐색한다. 단, 한정 조건을 통해 유망성을 점검하고 유망하지 않으면 해당 경우의 수를 배제한다.

N-Queen

N*N 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 경우의 수를 출력하는 문제이다.

나의 멍청했던 접근법

단순하게 2차원 배열을 생성하고 모든 값을 0으로 초기화한 후에, 퀸을 하나 두었을 때 공격 가능한 모든 칸을 1로 바꾸고 남아 있는 0 중에 하나에 퀸을 두고 또 1로 바꾸고... 이런식으로 구현을 하였다. 정말 단순하고 무식한 방법이었다. 모든 경우의 수를 보았기 때문에 시간은 엄청나게 소요되었고, 중복된 경우의 수도 횟수에 추가되어서 어마어마한 뻥튀기 결과값을 초래했다.

해답

우선, 2차원 배열을 생성할 필요가 없다. 1차원 배열을 생성하여 index를 행 값으로 보고, index에 위치한 값을 열 값으로 생각하면 된다. 반대로 생각해도 된다.

이 문제는 퀸들의 위치를 비교해서 같은 행인지, 같은 열인지, 대각선 상에 같이 있는지만 알면되기 때문에 2차원 배열이 필요없다.

이제 중요한 것은 한 행씩(또는 한 열씩) 살펴보면서 백트래킹을 수행하는 것이다.
우선 전체 코드는 다음과 같다.

#include<iostream>
using namespace std;

int N;
int board[15];
int res = 0;

bool possible(int currentRow) {
    // 이전 퀸들의 위치들
    for (int i = 0; i < currentRow; i++) {
        // 같은 열에 있거나 대각선 상에 있을 경우 false 반환
        if (board[i] == board[currentRow] || (currentRow - i) == abs(board[i] - board[currentRow])) {
            return false;
        }
    }

    return true;
}

void setQueen(int row) {
    if (row == N) {
        res++;
    }
    else {
        for (int col = 0; col < N; col++) {
            board[row] = col;

            if (possible(row)) {
                setQueen(row + 1);
            }
        }
    }
}

int main(void) {
    cin >> N;

    setQueen(0);

    cout << res << '\n';

    return 0;
}

possible 함수를 통해 다음 행에 퀸을 배치할 지 결정한다.

bool possible(int currentRow) {
    // 이전 퀸들의 위치
    for (int i = 0; i < currentRow; i++) {
        // 같은 열에 있거나 대각선 상에 있을 경우 false 반환
        if (board[i] == board[currentRow] || (currentRow - i) == abs(board[i] - board[currentRow])) {
            return false;
        }
    }

    return true;
}

for문을 통해 이전의 퀸들의 위치를 불러온다. 그리고, 현재 배치하려는 퀸의 위치와 비교하여 같은 열에 있거나 대각선 상에 있을 경우 다음 행에 퀸을 두지 않고 현재 과정(경우)를 배제한다.

출처: 위키피디아

현재 과정을 배제하면 직전(부모) 퀸의 위치를 바꾸어서 다른 과정을 살펴본다.
멍청했던 나의 접근법과 다르게 가망이 없으면 바로 손절(?)하여 시간을 절약할 수 있다.