[BOJ알고리즘, C++]#9663_N-Queen 문제, 백 트래킹

 

[BOJ 알고리즘, C++] #9663_N-Queen 문제, 백 트래킹

 

BOJ 알고리즘 문제 풀이, 9663_N-Queen 문제

백 트래킹을 통해 같은 행 혹은 대각선에 Queen이 위치하는지 확인합니다.

 

---

 

문제

 

풀이

1. 백 트래킹

• 깊이 우선 탐색을 기반한 알고리즘으로 "후보 해"의 집합에서 "최적해" 집합을 찾아내는 알고리즘입니다.
• 먼저, 깊이 우선 탐색은 트리 구조를 기반으로 수행되는 알고리즘입니다. 반면, 백 트래킹 알고리즘은 "조건"에 맞지 않는 정점 혹은 브랜치에 대한 "DFS"를 진행하지 않습니다!
• 정리하자면,  "백트래킹 알고리즘 = DFS + 특정 조건"이라고 볼 수 있겠습니다!

 

2. 백트래킹 알고리즘의 대표 문제, N-Queen  문제

1. N x N 체스판에서 퀸들이 서로 공격할 수 없도록 배치하는 방법은 각 행(Column)마다 하나의 퀸만 배치합니다.
2. 이때, 추가적으로 각 퀸들의 위치는 다른 퀸의 대각선에 위치해서도 안됩니다.
3. 정리하면, 후보 해에서 최적 해를 가려내기 위한 조건은 다른 행에 배치 + 대각선에 위치하지 않도록 하는 것이 됩니다

 

코드

#include <iostream>
using namespace std;

constexpr int MAX = 15;

int col[MAX];
int N, result=0;

// 최적 해를 가려내기 위한 조건
bool check(int colNum)
{
    for(int i=0; i<colNum; i++)
        if(col[i] == col[colNum] || abs(col[colNum] - col[i]) == colNum - i)
            return false;
    return true;
}

// 깊이 우선 탐색
void nqueen(int colNum)
{
    if(colNum == N)
        result++;
    else
    {
        for(int i=0; i<N; i++)
        {
            col[colNum] = i;
            // 최적 해를 찾아내기 위한 조건문
            if(check(colNum))
                nqueen(colNum+1);
        }   
    }
}

int main () {
    cin >> N;
    nqueen(0);
    cout << result << endl;
}

1. 이전에 공부했던 깊이 우선 탐색에서, 조건이 추가된 모습
2. 정점의 위치를 "Column", 즉 체스판의 행렬로 가정하면, 간단합니다.
3. 재귀 호출 탈출 조건문 + for 문을 통한 깊이 우선 탐색에서, for 문에서 추가적인 조건문을 통해 최적 해를 찾아냅니다