[백준] 9663번 N-Queen - C++

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

9663번: N-Queen

문제

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

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

입력

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

출력

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

---

   

     대표적인 백트래킹 문제인 N Queen 문제이다. 퀸들끼리 서로를 잡을 수 없게 하는 문제로 퀸은 가로 세로 대각선을 움직일 수 있다. 체스판 문제이지만 일차원 배열을 활용하여 arr[가로줄의 위치] = 세로줄의 위치로 나타낼 수 있다.

    이렇게 된다면 인덱스마다 값이 하나가 있기 때문에 가로줄은 겹칠 수가 없다. 따라서 세로줄과 대각선만 확인하면 된다.

세로줄을 확인하는 방법은 현재까지 채워진 배열에서 중복된 값이 나온다면 세로줄이 겹친것이다.

    대각선은 가로줄의 차와 세로줄의 차가 같은 경우 잡힌다고 볼 수 있다. 하지만 위와 아래 대각선 모두 되기 때문에 절댓값을 활용하여 가로의 차 == 세로의 차 이면 잡히는 경우이다.

    이렇게 인덱스를 재귀를 통해 늘려가면서 배열을 채운 다음 새로 들어간 수를 포함한 배열이 현재까지 유효한지 확인을 하면 재귀를 더 진행하고 유효하지 않다면 재귀를 그만두는 방식으로 최종 케이스에 도달하면 경우의 수를 증가하는 방식을 활용하면 답을 구할 수 있다. 

#include <iostream>

using namespace std;

int n, ans = 0;
int arr[16];

bool promising(int d){
    int i = -1;

    while(++i < d){
        if(arr[i] == arr[d] || abs(arr[i] - arr[d]) == d - i)
            return false;
    }
    return true;
}

void nqueens(int d){
    int i;
    if(d == n){
        ans++;
        return ;
    }
    for(int i = 0; i < n ; i++){
        arr[d] = i;
        if(promising(d))
            nqueens(d + 1);
    }
}

int main(){
    cin >> n;
    nqueens(0);
    cout << ans;
}

---

    42 서울 피신에서도 나온 문제로 대표적인 백트래킹 문제이다. 피신 기간 동안 동료평가를 통해 N Queen 문제를 포함한 다른 문제를 여러 번 동료들에게 설명을 하였다. 확실히 여러번 반복해서 설명하다 보니 체화가 된 것 같다. 코드를 짜는 것 이외에도 자신의 코드를 깔끔하게 설명하는 능력도 중요한 것 같다. 블로그를 시작한 이유기도 한데 앞으로도 코드를 깔끔하게 짜고 설명을 더 잘해보려고 노력해야겠다!