[백준 9663] N-Queen

🔗 알고리즘 문제

24일 진행했던 알고리즘 스터디에서 친구가 풀이하여준 문제 친구의 풀이를 듣고 직접 생각하며 다시 한번 풀어보았다. 설명을 들을 후 내가 다시 문제를 풀어보니 더욱 이해도 잘 되고 쉽게 풀 수 있었다.

문제 분석

백트래킹의 대표적인 문제로 불리는 N퀸 문제이다.

N퀸 문제는 N*N 크기의 체스판에서 N개의 퀸이 서로 공격할 수 없도록 배치하는 경우의 수를 찾아내는 문제이다.

발상 & 알고리즘 설계

친구의 설명대로 백트래킹을 이용해보기로 하였다.

가지치기 형식으로 현재 퀸을 놓는 자리가 유망하다면 그대로 진행해주었고, 유망하지 않다면 재귀 형식으로 다음 열로 넘어가 다시 유망성을 검사해주었다.

마지막 칸 까지 끊기지않고 도달했다면 경우의 수를 하나 증가시켜주었다.

코드

#include<iostream>
#include<cmath>

using namespace std;

int n;
int cols[15] = {};
int cnt = 0;

bool check(int r){
    for(int i = 0; i < r; i++){
        // 같은 열인지 검사
        if(cols[r] == cols[i])
            return false;

        // 대각선 검사
        if(abs(r - i) == abs(cols[r] - cols[i]))
            return false;
    }

    return true;
}

void FindQueen(int r){
    if(r == n){
        ++cnt;
        return;
    }

    for(int i = 0; i < n; i++){
        cols[r] = i;

        if(check(r)){
            FindQueen(r + 1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;

    FindQueen(0);

    cout << cnt;
}