[PS] BOJ 9663 : N-Queen

여름방학 이후 거의 처음으로 PS를 하는 중인데, 진짜 감 다 잃었다는게 체감이 확 된다.
일단 이번 방학 중으로 백준 플래티넘을 찍는게 목표이긴 한데... 가능할지는 모르겠다

어쨌든 오랜만에 PS하던 중 말로만 들었던 N-Queen 문제를 처음으로 풀어보게 되었다! 굉장히 유명한 문제이기도 하고 사실 한 번에 제대로 풀이를 생각해내지 못해서 따로 한 번 정리해야겠다는 생각이 들었다.

아마 앞으로도 블로그에 정리할 PS 관련 글들은 대부분 바로 푸는데 어려움이 있었던 문제들을 다루는 내용일 것이다.

N-Queen ?

N-Queen 문제는 한마디로 "크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수"를 구하는 문제이다.

퀸은 체스에서 가로, 세로, 대각선으로 모두 이동할 수 있는 매우 강력한 말이기 때문에 경우의 수가 몇 개 안 나올 것 같지만, N=8일 때 무려 distinct한 경우의 수가 92개나 나온다.

N에 따른 unique / distinct한 경우의 수를 정리한 표는 다음과 같다.

9663번 : N-Queen 백준 링크
해당 백준 문제에서는 N=1 ~ N=14인 경우의 distinct한 경우의 수를 계산해야 한다.

처음에 문제를 분석해보면서 백트래킹 / 재귀를 활용해야겠다는 사실은 쉽게 떠올릴 수 있었다. 하지만 정확하게 어떻게 구현해야 할 지는 스스로 떠올리지 못했다.

Algorithm : Backtracking

어쨌든 이 문제를 푸는 과정을 정리해보자.

일단 이 문제의 핵심은, N개의 퀸을 N X N 체스판에 놓는 것이기 때문에 각각의 퀸은 다른 행과 열에 존재해야 할 수 밖에 없다는 것이다!
이 점을 이용하면 백트래킹 과정을 조금 더 쉽게 설계할 수 있다.

바로 행이나 열 둘 중에 하나를 기준으로 잡고 해당 행이나 열에 퀸이 놓일 수 있는 위치를 계속해서 저장해나가며, 기존의 퀸 위치와 비교해나가면서 새롭게 퀸이 놓일 수 있는 위치를 찾는 것이다.
(나는 행을 기준으로 진행했다.)

예를 들어, 다음과 같은 그림으로 이해할 수 있겠다.

일단 우리는 0행에서 해당 과정을 시작한다. (solve(0)이라고 보면 된다)

먼저 (0, 0)에 퀸이 들어간다고 가정을 하면 이게 첫 번째로 들어가는 퀸이기 때문에 다른 기존의 퀸과 공격할 수 있는 자리에 있는지 비교할 필요 없으니 넘어갈 수 있다. 이렇게 되면 일단 카운트를 하나 올리고 이 퀸의 위치 정보를 저장한 다음 재귀 호출을 진행한다.
(이는 (0,1) ~ (0,7)에서도 동일할 것이다.)

자 이제, solve(1)에서 본다면, (즉 1행을 본다면)

우리는 1행에서 퀸을 놓을 수 있는 위치가 (1,2) ~ (1,7)임을 알 수 있다. 왜냐하면 (0,0)에 퀸이 있기 때문에 (1,0), (1,1)은 열과 대각선에서 서로 공격할 수 있는 위치이기 때문이다. 이를 반복문으로 열 index를 움직이면서 찾아주고 다시 (1,2) ~ (1,7)에서 solve(2)로 재귀가 들어갈 것이다.

이런 식으로 계속해서 재귀를 반복하며, cnt가 N=8과 같아진다면 정답 카운트를 하나 올리고 solve 함수를 종료시켜주면 되는 것이다. (즉, 마지막 행까지 도달하여 서로 공격하지 못하게 8개의 퀸이 모두 놓아진 상황이라는 것이다.)

이런 식으로 이중 반복문을 이용하여 각각의 경우에 대해 백트래킹을 실행하며 재귀적으로 코드를 작성하면 된다.

Code (C++)

여기서 구현을 위한 중요한 아이디어들이 몇 개 있는데, 실제 제출한 코드를 통해 한 번 보자.

#include <iostream>

using namespace std;

int ans = 0;
int N;
int board[15] = { 0, }; //x행의 board[x]열에 퀸이 놓여져있음

void solve(int cnt){

    if(cnt == N){
        ans++;
        return;
    }

    for(int col=0;col<N;col++){

        bool flag = true;

        for(int row=0;row<cnt;row++){
            if(board[row] == col || abs(cnt - row) == abs(col - board[row])){
                flag = false;
                break;
            }
        }

        if(flag){
            board[cnt] = col;
            solve(cnt+1);
        }

    }
}

int main(){

    cin >> N;
    solve(0);
    cout << ans << endl;

}

일단 퀸의 위치를 저장하기 위한 배열로 1차원 배열을 사용한다. x행의 arr[x]열에 퀸이 있다고 이해하면 된다.
이렇게 1차원 배열을 활용함으로써 반복문 구성을 조금 더 쉽게 할 수 있다.

코드의 핵심 부분은 바로 이중 for loop 부분인데,

일단 우리는 현재 solve 함수가 호출되었을 때 cnt행에 대해서 보고 있는 것 이라는 사실에 주목하자.

outer loop를 보면 col이 0~N-1까지로 움직여가며 모든 열에서 가능한 케이스를 찾는다.

각각의 col에 대해서 row라는 index로 다시 inner loop를 돌린다.
이때 row<cnt인 이유는, 지금 현재 퀸이 이미 놓여져있는 행은 0행~(cnt-1)행이기 때문에 이 행들에 대해서만 위치 비교를 해주면 되기 때문이다.

이때 어차피 두 퀸이 다른 행에 있는 건 당연하므로,
row행의 퀸이 col열에 있거나 (같은 열에 위치) /
row행의 퀸이 동일 대각선에 위치하는 경우 (절댓값으로 처리)
두 가지를 체크하면 된다.

만약 이 조건 체크에 걸렸다? 그러면 바로 반복문을 종료하고 탈출하면서 flag를 바꿔주면 된다.

결론적으로,
만약 flag가 false일 경우, board[cnt][col]에는 퀸을 놓지 못하는 것이고,
만약 flag가 true라면 board[cnt][col]에 퀸을 놓을 수 있기 때문에,
board[cnt] = col을 해주고, 다시 cnt+1로 재귀 호출을 해주면 되는 것이다.

마치며

이렇게 생각해보면 굉장히 쉬운 문제인데 막상 떠올리려고 하니 참 어렵다...
N-Queen 문제는 굉장히 유명한 문제니 꼭 머리 속에 담아두도록 해야겠다.
그리고 백트래킹 관련 문제는 많이 풀어보면서 어떻게 재귀함수를 설계할지 감을 좀 잡는게 중요할 것 같다.

그림 자료 출처 :
https://ko.wikipedia.org/wiki/%EC%97%AC%EB%8D%9F_%ED%80%B8_%EB%AC%B8%EC%A0%9C