문제 개요

n-Queens 문제는 n×n 크기의 체스판 위에 n개의 퀸을 배치하는 조합 최적화 문제입니다. 이때 어떤 두 퀸도 서로를 공격할 수 없어야 하며, 즉 같은 행, 열, 또는 대각선 상에 존재해서는 안 됩니다. 주어진 n에 대해 가능한 모든 배치를 출력하는 것이 목표입니다.

입력 및 출력 형식

• 입력: 정수 n (1 ≤ n ≤ 9)
• 출력: 각 해법은 n개의 줄로 구성되며, 각 줄은 길이 n의 문자열입니다. 빈 칸은 '.', 퀸의 위치는 'Q'로 표시합니다. 각 해법 사이에는 빈 줄이 삽입됩니다.

접근 전략

이 문제는 깊이 우선 탐색(DFS)과 백트래킹 기법을 사용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 한 행에 하나의 퀸만 배치할 수 있다는 점을 이용해, 각 행마다 적절한 열 위치를 탐색하는 것입니다. 이 과정에서 세 가지 제약 조건을 실시간으로 검사합니다:

• 같은 열에 중복 배치되지 않도록 함 (col[])
• 주대각선(↖↘ 방향)에 중복이 없도록 함 (dg[])
• 부대각선(↗↙ 방향)에 중복이 없도록 함 (udg[])

대각선 인덱스는 좌표 기반으로 계산됩니다. 예를 들어, (x, y) 위치의 주대각선 인덱스는 x + y, 부대각선 인덱스는 y - x + n으로 표현하여 음수가 되지 않도록 보정합니다.

해결 코드 (백트래킹 기반)

#include <iostream>
using namespace std;

const int MAX_SIZE = 20;
int n;
char board[MAX_SIZE][MAX_SIZE];
bool columnUsed[MAX_SIZE];           // 열 사용 여부
bool mainDiagUsed[MAX_SIZE * 2];     // 주대각선 (x + y)
bool antiDiagUsed[MAX_SIZE * 2];     // 부대각선 (y - x + n)

void solve(int row) {
    if (row == n) {
        for (int i = 0; i < n; ++i) {
            cout << board[i] << endl;
        }
        cout << endl;
        return;
    }

    for (int col = 0; col < n; ++col) {
        int diag1 = row + col;
        int diag2 = col - row + n;

        if (!columnUsed[col] && !mainDiagUsed[diag1] && !antiDiagUsed[diag2]) {
            // 현재 위치에 퀸 배치
            board[row][col] = 'Q';
            columnUsed[col] = mainDiagUsed[diag1] = antiDiagUsed[diag2] = true;

            solve(row + 1);

            // 상태 복구 (백트래킹)
            columnUsed[col] = mainDiagUsed[diag1] = antiDiagUsed[diag2] = false;
            board[row][col] = '.';
        }
    }
}

int main() {
    cin >> n;

    // 초기화
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            board[i][j] = '.';
        }
    }

    solve(0);
    return 0;
}

입력 예제

4

출력 예제

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

알고리즘 분석

• 시간 복잡도: O(n!) — 매 행에서 가능한 열 선택지를 줄여나가므로 완전 탐색보다 효율적입니다.
• 공간 복잡도: O(n) — 방문 상태 배열과 재귀 스택 깊이가 최대 n입니다.

이 방법은 n이 작을 때(≤9) 매우 효과적이며, 백트래킹과 상태 추적을 통한 조기 차단(pruning)으로 불필요한 탐색을 크게 줄입니다.