[백준 9663번] N-Queen

개요

백준 9663번 문제이다. 앞서 풀었던 [백준 15649번] N과 M (1)과 같은 백트래킹과 recursion을 사용하는 문제이다.

문제

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

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

입력

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

출력

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

접근

체스판의 한 행마다 하나의 퀸만 올 수 있으므로 dfs의 레벨(깊이)은 체스판의 행으로 정하고, 각 행의 각 칸마다 퀸을 놓을 수 있는지 체크하며 가능하다면 다음 레벨로 넘어가는 식으로 생각해 보았다.

앞서 풀었던 N과 M문제와 매우 흡사한 알고리즘이었다.

코드

#include <bits/stdc++.h>

using namespace std;

int ans;
int n;
int board[16][16];

bool check_conflict(int h, int w)
{
    for (int i = 0; i < n; i++)
    {
        if (board[h][i] || board[i][w])
            return false;
        if (0 <= h - w + i && h - w + i < n)
        {
            if (board[h - w + i][i])
                return false;
        }
        if (0 <= h + w - i && h + w - i < n)
        {
            if (board[h + w - i][i])
                return false;
        }
    }
    return true;
}

void dfs(int l)
{
    if (l >= n)
    {
        ans += 1;
        return;
    }
    
    for (int i = 0; i < n; i++)
    {
        if (check_conflict(l, i))
        {
            board[l][i] = 1;
            dfs(l + 1);
            board[l][i] = 0;
        }
    }
}

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> n;
    dfs(0);
    cout << ans;

    return 0;
}