[c++] 백준 #9663 N-Queen

너무 유명한 brute force 문제이고, 2~3년 전 쯤 2차원 행렬로 표시해서 풀다가 구현을 잘못해서 잘 안되니 포기했던 문제를 친구가 풀이방법을 설명해줘서 낼름 듣고 바로 푼 문제이다.

내용은 NxN 체스판 위에 N개의 퀸이 서로 공격할 수 없게(가로, 세로, 대각선 x) 두는 경우의 수를 계산하는 것이다.

 

www.acmicpc.net/problem/9663 

9663번: N-Queen

<풀이>

queen의 가로, 혹은 세로 좌표가 다른 queen과 겹치지 않으면 되기 때문에 굳이 2차원 배열을 만들 필요가 없다는 것이 간단한 구현의 포인트이다. 가령 chess[i][j] = 1을 queen의 자리를 표시할 때 썼다면, col[i] = j라는 식으로 표현해도 전혀 문제가 없다. 또한, 각 행마다 퀸을 하나씩 놓는 방법을 생각해보면, 아직 놓지 않은 자리를 확인할 필요는 없으므로, 자신의 이전 행의 퀸들의 위치와 이번에 놓을 퀸의 위치만 비교하면 된다. 대각선에 퀸이 있는지 확인할 때에는 x좌표의 차이의 절대값, y좌표의 차이의 절댓값을 비교하면 굳이 왼쪽 대각선 혹은 오른쪽 대각선을 별도로 확인하지 않아도 된다. 그래서 0번째 행부터 N-1번째 행까지 차곡차곡 퀸을 넣고, n_queen의 인자가 N이 되면 모든 퀸이 합당하게 다 채워진 것이기 때문에 경우의 수를 증가시킨다. 이번 문제에서는 답의 대칭성을 고려하지 않기 때문에 이렇게 풀어도 무방하다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define pb push_back

int col[16];
int N = 0;
int Q = 0;

bool is_possible(int n){
    for (int i=0; i<n;i++){
        if (col[i] == col[n] || abs(i-n) == abs(col[i]-col[n])){
            return false;
        }
    }
    return true;
}

void n_queen(int n){
    if (n==N){
        Q++;
        return;
    }

    for(int i=0; i<N;i++){
        col[n] = i;
        if (is_possible(n)){
            n_queen(n+1);
        }
    }
}

int main(){
    cin >> N;
    n_queen(0);
    cout << Q << '\n';
    return 0;
}