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

9663번: N-Queen

문제

코드

/**
 * baekjoon - 9663
 * backtracking, bruteforcing */

#include <iostream>
#include <cmath>
#define fio ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

int n;
int col[15];
int cnt = 0;

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

    return true;
}

void nqueen(int num){
    if (num == n){
        cnt++;
        return;
    }

    for (int i = 0; i < n; i++){
        col[num] = i; // (num, i)
        if (isPromising(num)) nqueen(num+1);
    }

}

int main(){
    // input
    fio;
    cin >> n;

    // sol
    nqueen(0);
    cout << cnt;
    return 0;
}

해설

대표적인 백트레킹 문제로 퀸을 놓은 곳의 가로, 세로, 대각선에 퀸을 놓지 않는 경우의 수를 구하는 문제이다. N의 개수만큼 단계를 나누어서 가능한 경우의 수를 따라가 해당 경우가 타당한지를 체크해야한다. isPromising 함수를 통해 가로, 세로, 대각선에 존재하는지를 판단할 수 있고, 만약 존재한다면 false, 존재하지 않는 다면 true를 넘겨주어 다음 단계로 넘어갈 수 있는 결정적인 역할을 해준다. 이렇게 N번 만큼 반복하여 성공하면 cnt 횟수를 하나 증가해 경우의 수를 세어나가면 된다.