[백준/C,C++] 9663번: N-Queen

www.acmicpc.net/problem/9663

9663번: N-Queen

백트래킹 문제로 되게 유명한 N-Queen 문제입니다. 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제인데, 이게 왜 트리 탐색 알고리즘이 필요한가 싶지만, 트리의 형태로 문제를 나타낼 수 있습니다. 입력값으로 4가 들어온 경우 4x4 체스판 위에 퀸 4개를 서로 공격할 수 없게 두어야 합니다.

예를 들어, 위의 그림을 보면 첫 번째 열에서 2번째 칸에 퀸을 놓았다고 치면 직선에 놓인 2열 2번째 칸과 대각선에 놓인 2열 1, 3번째 칸엔 퀸을 놓을 수 없습니다. 서로 공격이 가능하니까요. 위처럼 이전에 놓인 퀸의 공격 가능 지역인지 확인하며 노드를 선택한다면 모든 퀸을 체스판 위에 올려둘 수 있습니다.

void dfs(int row)
{
    
    if (row == n + 1) {
        res++;
        return;
    }
    for (int col = 1; col <= n; col++) {
        cols[row] = col;
        if (check(row, col)) {
            dfs(row + 1);
        }
    }
}

먼저 dfs 함수입니다. 현재 row(열)를 입력받아 col(행)을 돌며 check 함수를 통과한 경우 해당 칸에 퀸을 놓게 됩니다. 즉 check 함수가 이전 열에 놓인 퀸의 공격이 불가능한 칸인지 검사하는 함수라고 보시면 됩니다. n열까지 모두 골랐다면(row == n + 1) res값(퀸을 서로 공격할 수 없게 놓는 경우의 수)을 1 증가 시키고 리턴합니다. 이제 조건인 check 함수가 중요한데, 일단 코드는 아래와 같습니다.

bool check(int row, int col)
{
    for (int i = 1; i < row; i++) {
        if (cols[i] == col || abs(i - row) == abs(cols[i] - col)) {
            return false;
        }
    }
    return true;
}

이전 열에 놓인 퀸과 직선인 칸이라면(cols[i] == col) 퀸을 놓을 수 없습니다. 또한 이전 열에 놓인 퀸과 대각인 칸이라도 해당 칸에는 퀸을 놓을 수 없습니다. 대각인 칸은 abs(i - row) == abs(cols[i] - col) 과 같은 식으로 검사할 수 있는데, 이전 열에 놓인 퀸과 열과 행의 차이가 같은 칸이라면 대각에 위치하는 칸입니다.

#include<iostream>
#include<vector>

using namespace std;

#define SIZE 15

int n;
int res;
int cols[SIZE];

bool check(int row, int col)
{
    for (int i = 1; i < row; i++) {
        if (cols[i] == col || abs(i - row) == abs(cols[i] - col)) {
            return false;
        }
    }
    return true;
}

void dfs(int row)
{
    
    if (row == n + 1) {
        res++;
        return;
    }
    for (int col = 1; col <= n; col++) {
        cols[row] = col;
        if (check(row, col)) {
            dfs(row + 1);
        }
    }
}

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

    cin >> n;

    dfs(1);

    cout << res;

    return 0;
}