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

🔗문제 보러가기

9663번: N-Queen

 

 

문제 설명

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

---

입력

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

 

---

출력

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

 

---

예제 입출력

 

---

풀이 전략

\( N \times N\) 체스판에서 퀸이 서로 공격을 하지 못하게 놓는 경우의 수를 구하는 문제입니다.

퀸은 자신이 놓인 위치로부터 같은 일자 선상 및 대각선상까지 공격할 수 있는 사기 체스말입니다. (그에 비해 킹은...)

즉, 퀸이 놓인 위치가 다음과 같다면, 빨간색으로 칠해진 위치는 피해야 합니다.

 

4 X 4 크기의 체스판에서 퀸 하나를 놓았을 때, 피해야 하는 경로(빨간색)

 

그렇기에, 퀸을 놓을 수 있는 모든 경우의 수를 구하려면 현재 좌표에 퀸을 놓았을 때 퀸 공격로 상에 또 다른 퀸이 있는지 검사하는 게 필요합니다. 사실상 상하좌우, 왼위 대각, 왼아래 대각, 오른위 대각, 오른아래 대각 이렇게 총 8개의 공격로가 존재하죠.

 

처음에는 저렇게 8방향을 모두 검사하는 코드를 짰었는데, 이렇게 되면 시간 초과가 발생하더라구요.

그래서 시간을 줄일 수 있는 방안을 더 알아보았습니다.

 

 

시간 소요를 줄이기 위한 방안들

저는 (0, 0)에서 시작하여 열(Column)을 우선으로 탐색하는 방식으로 진행했습니다.
예를 들어, 4 X 4 체스판이라면, (0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (2, 0) ... 이런 식으로 열을 먼저 검사한다는 의미입니다.

 

검사하는 방식이 이러하다면, 다음 사항들을 고려해볼 수 있습니다.

• 한 행(Row)에 있는 열(Column)들 중 어떤 곳이라 퀸을 하나 배치한다면, 그 행에는 더 이상 퀸을 배치할 수 없다.
  
  • 즉, 해당 행에 퀸을 배치했다면 다음 행으로 넘어가서 탐색을 시작한다.

0행 0열에 퀸을 배치했으므로, 0행 1, 2, 3열쪽으로 배치 진행을 할 필요가 없다.

 

• 체스판 위쪽부터 퀸 배치를 시작하므로, 아래쪽 방향 탐색을 할 필요가 없다.
  • 체스판 위쪽부터 퀸 배치를 하므로, 체스판 아래쪽에는 당연히 퀸이 없으니 탐색을 할 필요가 없다.
  • 즉, 탐색 방향은 위, 왼쪽 위 대각, 오른쪽 위 대각 이렇게 세 군데만 탐색하면 된다.

현재 배치 진행 중인 위치가 (1, 1)이므로 그 아래 행들(2, 3)들에는 당연히 퀸이 없어 탐색할 필요 X

 

이제 백트래킹(Backtracking)을 진행하며, 위 과정들을 반복하면 됩니다. 시뮬레이션 과정을 한 번 첨부해봤습니다.

 

 

---

소스 코드 및 결과

#include <iostream>
#include <vector>
using namespace std;

bool CheckQueenExisting(vector<vector<bool>>& chessBoard, int row, int column) {
    for (int i = 0; i < row; i++) {
        if (chessBoard[i][column])     // 맨 위 행부터 현재 행까지 같은 열에 퀸 있는지 검사
            return true;

        int colDiff = row - i;
        if (column - colDiff >= 0 && chessBoard[i][column - colDiff])  // 왼쪽 위 대각선 검사
            return true;

        if (column + colDiff < chessBoard.size() && chessBoard[i][column + colDiff])  // 오른쪽 위 대각선 검사
            return true;
    }
    return false;
}


int NQueen(vector<vector<bool>>& chessBoard, int currentRow) {
    if (currentRow == chessBoard.size())
        return 1;

    int answer = 0;
    for (int column = 0; column < chessBoard.size(); column++) {
        if (!CheckQueenExisting(chessBoard, currentRow, column)) {
            chessBoard[currentRow][column] = true;
            answer += NQueen(chessBoard, currentRow + 1);
            chessBoard[currentRow][column] = false;
        }
    }
    return answer;
}

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

    int N;
    cin >> N;

    vector<vector<bool>> chessBoard(N, vector<bool>(N, false));
    cout << NQueen(chessBoard, 0);
    return 0;
}