백준 9663번 [N-Queen](C++)-yes6686- 티스토리

백준 문제 풀이: 9663 [N-Queen]

---

문제 링크: https://www.acmicpc.net/problem/9663

문제 설명:

N-Queen 문제는 N×N 체스판 위에 N개의 퀸을 서로 공격하지 못하도록 배치하는 경우의 수를 구하는 문제입니다. 퀸은 가로, 세로, 대각선으로 공격할 수 있습니다.

입력:

• 첫째 줄에 정수 N이 주어집니다. (1 ≤ N ≤ 15)

출력:

• N개의 퀸을 서로 공격하지 못하게 배치하는 경우의 수를 출력합니다.

---

문제 해결 코드

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

int n;
int column[15]; // 세로 열 체크
int diag1[30];  // 오른쪽 아래 대각선 체크
int diag2[30];  // 왼쪽 아래 대각선 체크
int result = 0;

void backtrack(int row) {
    if (row == n) {
        result++; // 퀸을 모두 배치하면 경우의 수 증가
        return;
    }

    for (int col = 0; col < n; col++) {
        if (column[col] || diag1[row + col] || diag2[row - col + n - 1]) {
            continue; // 열, 대각선 중 하나라도 겹치면 배치 불가
        }

        // 현재 위치에 퀸 배치
        column[col] = diag1[row + col] = diag2[row - col + n - 1] = 1;
        backtrack(row + 1); // 다음 행으로 이동
        column[col] = diag1[row + col] = diag2[row - col + n - 1] = 0; // 백트래킹
    }
}

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

    cin >> n;

    backtrack(0); // 0번째 행부터 시작
    cout << result << '\n';

    return 0;
}

예제

입력:
8

출력:
92

입력:
4

출력:
2

---

코드 설명

• 배열 활용:
  • column: 현재 열에 퀸이 있는지 체크
  • diag1: 오른쪽 아래 대각선 체크 (row + col로 인덱스 계산)
  • diag2: 왼쪽 아래 대각선 체크 (row - col + n - 1로 인덱스 계산)
• 백트래킹:
  • 행별로 한 번씩 퀸을 배치하며, 가능한 열과 대각선을 확인합니다.
  • 퀸을 배치한 후, 다음 행으로 이동합니다.
  • 모든 행에 퀸을 배치한 경우 경우의 수를 증가시킵니다.
• 효율적인 체크:
  • 배열을 이용해 열과 대각선의 상태를 저장하여, 매번 조건을 빠르게 확인할 수 있습니다.

시간 복잡도

• 백트래킹을 사용하며, 최악의 경우 N!에 가까운 탐색을 수행합니다.
• 효율적인 대각선 및 열 체크로 실제 계산량은 크게 감소합니다.

---

결과

코드는 N-Queen 문제의 모든 경우를 정확히 탐색하며, 백트래킹과 효율적인 체크 배열을 활용하여 최적화된 결과를 제공합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!