[BOJ] C++ 9633 N-Queen - 백트래킹 구현하기

9663번: N-Queen

예제

8

ans : 92

---

백트래킹에 익숙하지 않은 분들은

[알고리즘] 백트래킹 - 재귀를 통한 구현과 응용 문제

이 글을 꼭 먼저 읽어보시기 바랍니다.

---

먼저 적당히 4개 정도의 퀸을 손으로 놔보자. 처음에 퀸 하나를 0행 0열에 두고 밑으로 내려가면서 다음에 둘 퀸 위치를 하나하나 탐색해 보는 식으로 풀 수 있고 이 방법이 가장 쉽다. 이런 식으로 풀다 보면 당연히 한 행에 하나의 퀸만 들어가는 것을 알게 되고 이 방식으로 구현할 수 있을 것이다.

 

백트래킹은 재귀를 통해 구현되므로 기본 구조를 짜보자.

 

• base condition : 퀸 수가 N이면 종료
• 함수 형태 : void func(int Q) : Q번째 퀸을 Q항에 서로 공격할 수 없게 두기
• 재귀식 : Q개의 퀸을 놓았으면 Q + 1 번째 퀸을 놓을 수 있는 곳을 체크한다.

이때 Q번째 퀸을 어디에 놓아도되는지 체크하는 부분이 문제가 된다. 우선 행은 정해져 있으므로 위험한 열과 대각선을 체크해 보자.

1. 위험한 열 체크 : visited_vertical [] : (x, y)에 퀸이 있으면 y열은 모두 위험하다. 이를 visited_vertical [y] = true로 기록해 두자.
2. 오른쪽 위 방향 대각선 체크 : visited_horizontal1 : 오른쪽 위 대각선의 좌표를 보면 당연하게도 합이 같다. 따라서 (x, y)에 퀸이 있으면 i+j = x+y인 (i, j)는 모두 위험하다. visited_horizontal [x+y] = true로 기록해 두자.
3. 오른쪽 아래 방향 대각선 체크 : visited_horizontal2 : 오른쪽 아래 대각선의 좌표를 x-y의 값이 모두 같다. 따라서 (x, y)에 퀸이 있으면 i-j = x-y인 (i, j)는 모두 위험하다. visited_horizontal [x-y+n-1] = true로 기록해 두자. n-1을 더하는 이유는 양수로 만들기 위함이다.

이제 func(Q)의 동작은 (Q, 0) ~ (Q, n-1)까지 퀸을 놓을 수 있는지 체크하는 것을 알 수 있다. 그대로 구현해 주면 된다.

/** BacKTracKing 9663 N-Queen **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define MAX 15
using namespace std;

int n;
int res = 0;
bool visited_vertical[40];
bool visited_diagonal1[40];
bool visited_diagonal2[40];

void func(int Q)
{
    // Q번째 퀸을 놓으면 된다.
    if (Q == n)
    {
        // base condition
        res++;
        return;
    }

    for (int i = 0; i < n; i++)
    {
        // Q행 i열에 퀸을 놓을 수 있는지 체크
        if (visited_vertical[i])
            continue;
        if (visited_diagonal1[Q + i])
            continue;
        if (visited_diagonal2[Q - i + n - 1])
            continue;
        // 놓을 수 있으므로 놓고 방문 체크
        visited_vertical[i] = true;
        visited_diagonal1[Q + i] = true;
        visited_diagonal2[Q - i + n - 1] = true;
        func(Q + 1);

        // Q번째 퀸을 다 놓아 봤으므로 다시 초기화
        visited_vertical[i] = false;
        visited_diagonal1[Q + i] = false;
        visited_diagonal2[Q - i + n - 1] = false;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    func(0);
    cout << res;
}

visited_ 배열 시리즈의 크기가 MAX가 아닌 것만 조심하자.