[BOJ 9663] N-Queen(C++)

N-Queen (Gold 5)

문제

전체 문제 보기

9663번: N-Queen

접근법

N-Queen 문제는 Backtracking을 활용하여 풀 수 있습니다. Backtracking의 알고리즘은 항상 다음과 같은 패턴으로 구현할 수 있습니다.

• 탈출 조건 확인
• 반복문을 활용한 모든 브랜치 탐색
• 조건에 만족하는 브랜치만 재귀적으로 탐색

N-Queen 문제 또한 위의 방식으로 풀이할 수 있습니다. 일반적인 Backtracking 알고리즘보다 유효성 검사 부분이 까다롭고 가지치기를 효과적으로 하기 위한 접근법이 생각해내기 어렵기 때문에 난이도가 높은 편에 속합니다. 우선 Backtracking 코드를 보며 설명하겠습니다.

int Backtracking(Check& check, int N, int row)
{
    if (row == N) return 1;

    int retval{};
    for (int col = 0; col < N; ++col)
    {
        if (IsValid(check, row, col) == false) continue;
        AddQueen(check, row, col);
        retval += Backtracking(check, N, row + 1);
        RemoveQueen(check, row, col);
    }

    return retval;
}

탈출 조건 확인

임의의 행에 퀸이 위치하게 되면 해당 행에는 더이상 퀸이 위치할 수 없습니다. 그래서 Backtracking을 0번째 row에서 N-1번째 row까지 탐색을 진행합니다. 만약 row의 크기가 N과 같아졌다면 N-1 위치까지 유효한 위치에 퀸을 배치할 수 있었다는 뜻이기 때문에 1을 반환해줍니다.

가지 치기

백트레킹 알고리즘은 가능한 모든 경우에 대해서 가지 치기를 진행합니다. 이때 다음 퀸이 위치할 수 있는 열을 기준으로 가지치기를 진행합니다. 다음 퀸이 위치할 수 있는 열은 0번 col부터 N-1번 col까지 있습니다. for문에서 모든 열의 경우에 대해서 탐색을 진행해줍니다.

유효성 검사

퀸은 가로 세로 대각선 모든 경우로 공격을 진행할 수 있습니다. 임의의 위치에 퀸을 놓으려고할 때 해당 위치에 퀸을 놓을 수 있는지 없는지 검사하는 부분입니다. 이 부분을 선형 탐색으로 진행하게 될 경우 모든 체스판을 탐색해야 하기 때문에 탐색에 상당히 오래 걸리게 됩니다. 이를 해시 맵을 활용하여 \(O(1)\)회 만에 시행할 수 있습니다. 여기서는 성능을 위해 해시 맵 대신 배열과 해싱 간단한 해싱 함수를 구현하여 사용하였습니다. 접근 방법은 다음과 같습니다.

• 백트래킹의 각 깊이는 별도의 row로 진행되기 때문에 동일한 row에 대해서는 검사할 필요가 없습니다.
• col 에 대해서는 N개의 bool type 배열로 유효성 검사를 진행합니다.
• 좌상단 → 우하단 대각선은 동일한 대각선 상 위에서는 항상 col - row 값이 일정하다는 규칙을 활용하여 해싱 함수를 구현합니다.
• 우상단 → 좌하단 대각선은 동일한 대각선 상 위에서는 항상 col + row 값이 일정하다는 규칙을 활용하여 해싱 함수를 구현합니다.

우선 유효성 검사를 위해서 사용될 배열들을 구조체로 다음과 같이 추상화하여 사용할 수 있습니다.

struct Check {
    Check(int n)
        : N(n)
        , col_set(n)
        , dia_1(2*n - 1)
        , dia_2(2*n - 1)
    {}
    int N;
    vector<bool> col_set; // 열 집합
    vector<bool> dia_1;   // 좌상단에서 우하단
    vector<bool> dia_2;   // 좌하단에서 우상단
};

위 규칙을 활용하여 다음과 같이 해싱 함수를 만들 수 있습니다.

// 좌상단 -> 우하단 대각선 해싱
int GetDia_1_index(const Check& check, int row, int col)
{
    return col - row + check.N - 1;
}
// 좌하단 -> 우상단 대각선 해싱
int GetDia_2_index(const Check& check, int row, int col)
{
    return col + row;
}

그리고 아래와 같이 유효성 검사 함수와 퀸을 추가하고 삭제할 수 있는 IsValid, AddQueen, RemoveQueen 함수를 만들 수 있습니다.

 

IsValid 함수 

bool IsValid(Check& check, int row, int col)
{
    // 열 방향 확인
    int idx = col;
    if (check.col_set[idx]) return false;

    // 좌상단 -> 우하단 대각선 확인
    idx = GetDia_1_index(check, row, col);
    if (check.dia_1[idx]) return false;

    // 좌하단 -> 우상단 대각선 확인
    idx = GetDia_2_index(check, row, col);
    if (check.dia_2[idx]) return false;

    return true;
}

 

AddQueen 함수

void AddQueen(Check& check, int row, int col)
{
    // 열 방향 마킹
    int idx = col;
    check.col_set[idx] = true;

    // 좌상단 -> 우하단 대각선 마킹
    idx = GetDia_1_index(check, row, col);
    check.dia_1[idx] = true;

    // 좌하단 -> 우상단 대각선 마킹
    idx = GetDia_2_index(check, row, col);
    check.dia_2[idx] = true;
}

 

RemoveQueen 함수

void RemoveQueen(Check& check, int row, int col)
{
    // 열 방향 마킹 삭제
    int idx = col;
    check.col_set[idx] = false;

    // 좌상단 -> 우하단 대각선 마킹 삭제
    idx = GetDia_1_index(check, row, col);
    check.dia_1[idx] = false;

    // 좌하단 -> 우상단 대각선 마킹 삭제
    idx = GetDia_2_index(check, row, col);
    check.dia_2[idx] = false;
}

이렇게 구현한 IsValid, AddQueen, RemoveQueen 함수들을 활용하여 전체의 경우를 효율적으로 탐색할 수 있습니다.

전체 코드

아래와 같이 전체 Quene이 위치할 수 있는 경우의 수를 계산하는 프로그램을 작성할 수 있습니다.

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;
struct Check {
    Check(int n)
        : N(n)
        , col_set(n)
        , dia_1(2*n - 1)
        , dia_2(2*n - 1)
    {}
    int N;
    vector<bool> col_set;
    vector<bool> dia_1;
    vector<bool> dia_2;
};
// 좌상단 -> 우하단 대각선 해싱
int GetDia_1_index(const Check& check, int row, int col)
{
    return col - row + check.N - 1;
}
// 좌하단 -> 우상단 대각선 해싱
int GetDia_2_index(const Check& check, int row, int col)
{
    return col + row;
}
bool IsValid(Check& check, int row, int col)
{
    // 열 방향 확인
    int idx = col;
    if (check.col_set[idx]) return false;

    // 좌상단 -> 우하단 대각선 확인
    idx = GetDia_1_index(check, row, col);
    if (check.dia_1[idx]) return false;

    // 좌하단 -> 우상단 대각선 확인
    idx = GetDia_2_index(check, row, col);
    if (check.dia_2[idx]) return false;

    return true;
}
void AddQueen(Check& check, int row, int col)
{
    // 열 방향 마킹
    int idx = col;
    check.col_set[idx] = true;

    // 좌상단 -> 우하단 대각선 마킹
    idx = GetDia_1_index(check, row, col);
    check.dia_1[idx] = true;

    // 좌하단 -> 우상단 대각선 마킹
    idx = GetDia_2_index(check, row, col);
    check.dia_2[idx] = true;
}
void RemoveQueen(Check& check, int row, int col)
{
    // 열 방향 마킹 삭제
    int idx = col;
    check.col_set[idx] = false;

    // 좌상단 -> 우하단 대각선 마킹 삭제
    idx = GetDia_1_index(check, row, col);
    check.dia_1[idx] = false;

    // 좌하단 -> 우상단 대각선 마킹 삭제
    idx = GetDia_2_index(check, row, col);
    check.dia_2[idx] = false;
}
int Backtracking(Check& check, int N, int row)
{
    if (row == N) return 1;

    int retval{};
    for (int col = 0; col < N; ++col)
    {
        if (IsValid(check, row, col) == false) continue;
        AddQueen(check, row, col);
        retval += Backtracking(check, N, row + 1);
        RemoveQueen(check, row, col);
    }

    return retval;
}
int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N; //  (1 ≤ N < 15)
    cin >> N;
    Check check(N);
    cout << Backtracking(check, N, 0);

    return 0;
}