백준 9663 - N-Queens

백트래킹 | 2026.03.16

---

🧩 문제 이해

N×N 체스판에 퀸을 N개 놓는데, 퀸끼리 서로 공격할 수 없게 배치하는 경우의 수를 구하는 문제다.

퀸은 상하좌우 + 대각선 방향으로 거리 제한 없이 이동하기 때문에, 같은 행 / 열 / 대각선에 두 퀸이 있으면 안 된다.

---

💡 핵심 관찰

• N개의 퀸을 N개의 행에 놓아야 하므로, 각 행에 퀸이 정확히 1개씩 있어야 한다.
• 즉, 행을 하나씩 내려가며 어느 열에 퀸을 놓을지 결정하면 된다 → DFS + 백트래킹

---

🔄 백트래킹이란?

가능성이 없는 경우를 조기에 차단(가지치기)하면서 DFS로 탐색하는 방식이다.

일반 DFS는 끝까지 가보고 틀리면 돌아오지만, 백트래킹은 중간에 "이건 답이 될 수 없다"고 판단되면 즉시 되돌아온다.

---

📐 충돌 조건 수학적으로 표현하기

두 퀸의 좌표가 (r1, c1), (r2, c2)일 때:

같은 열     : c1 == c2
↘ 대각선   : r1 - c1 == r2 - c2
↗ 대각선   : r1 + c1 == r2 + c2

이걸 bool 배열 3개로 관리하면 충돌 체크를 O(1) 에 할 수 있다:

col[c]        // 열 체크
diag1[r+c]    // ↗ 대각선 (r+c 값이 같으면 같은 대각선)
diag2[r-c+N]  // ↘ 대각선 (r-c 값이 같으면 같은 대각선, 음수 보정 +N)

배열 크기 계산

| 배열 | 범위 | 크기 | |------|------|------| | col | 0 ~ N-1 | 15 | | diag1[r+c] | 0 ~ 28 | 29 | | diag2[r-c+N] | 0 ~ 28 | 29 |

---

✅ 최종 코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int N, cnt = 0;
vector<bool> col(15, false);
vector<bool> diag1(29, false);
vector<bool> diag2(29, false);

void track(int r) {
    if (r == N) {
        cnt++;
        return;
    }
    for (int i = 0; i < N; i++) {
        if (!col[i] && !diag1[r+i] && !diag2[r-i+N]) {
            col[i] = true;
            diag1[r+i] = true;
            diag2[r-i+N] = true;
            track(r + 1);
            col[i] = false;
            diag1[r+i] = false;
            diag2[r-i+N] = false;
        }
    }
}

int main() {
    cin >> N;
    track(0);
    cout << cnt;
}

---

🗣️ 회고

• 처음엔 퀸의 이동범위를 킹이랑 헷갈렸다. 퀸은 방향만 같으면 거리 무제한.
• 대각선 조건을 NxN visited로 구현하려다가, 배열 3개 + O(1) 체크 방식이 훨씬 깔끔하다는 걸 깨달았다.
• diag2[r-c+N]에서 r-c가 음수가 될 수 있으니 +N으로 보정하는 게 핵심 디테일이었다.
• 전역 bool 배열을 false로 명시 초기화해야 한다는 것도 챙겨야 할 부분.