[C++] 백준 9663 N_Queen

코드

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

int N;
int answer;
vector<int> visited(15, -1);

bool Check(int qCnt)
{
    for (int i = 0; i < qCnt; i++)
    {
        if (visited[qCnt] == visited[i] || abs(qCnt - i) == abs(visited[qCnt] - visited[i]))
            return false;
    }
    return true;
}

void N_Queen(int qCnt)
{
    if (qCnt == N)
    {
        answer++;
        return;
    }

    for (int j = 0; j < N; j++)
    {
        visited[qCnt] = j;
        if (Check(qCnt))
            N_Queen(qCnt + 1);
    }
}

int main()
{
    cin >> N;
    N_Queen(0);
    cout << answer << "\n";
}

---

코드 설명

✅ 문제 요약
N x N 체스판이 있다
N개의 퀸을 서로 공격하지 않도록 배치해야 함.
퀸은 가로, 세로, 대각선으로 공격할 수 있다.
가능한 배치의 경우의 수를 구하는 문제.

🧠 핵심 개념
퀸이 서로 공격하지 않는 조건
퀸끼리 다음 조건을 피해야 함:
1.같은 열(column) 에 있으면 안 됨
2.같은 왼쪽 ↙ 대각선 또는 오른쪽 ↘ 대각선 에 있으면 안 됨

// 현재 퀸(qCnt번째)을 놓을 때, 이전 퀸들과 충돌하는지 확인하는 함수
bool Check(int qCnt)
{
    for (int i = 0; i < qCnt; i++)
    {
        // 같은 열에 놓았는지 확인
        if (visited[qCnt] == visited[i])
            return false;

        // 대각선에 있는지 확인 (행 차이 == 열 차이면 대각선에 있음)
        if (abs(qCnt - i) == abs(visited[qCnt] - visited[i]))
            return false;
    }
    return true;
}

📐 대각선 판별 핵심
✨ 핵심 공식:
퀸 A와 퀸 B가 있을 때,
|행 차이| == |열 차이|
면 같은 대각선에 있다

---

🧊 예시: 8x8 체스판

퀸 A 위치: (2행, 3열)

퀸 B 위치: (5행, 6열)

📏 계산
|행 차이| = |5 - 2| = 3
|열 차이| = |6 - 3| = 3

✔️ 같은 대각선에 있음 → 서로 공격 가능!

열 →
  0 1 2 3 4 5 6 7
0 . . . . . . . .
1 . . . . . . . .
2 . . . Q . . . .   ← 퀸 A (2, 3)
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . Q .   ← 퀸 B (5, 6)
6 . . . . . . . .
7 . . . . . . . .

↘ 방향으로 쭉 따라가면 (5,6)에 퀸 B가 있어 → 같은 대각선!

---

🎯 코드 속 대각선 체크 다시 보기

if (abs(qCnt - i) == abs(visited[qCnt] - visited[i]))
    return false; // 대각선 충돌

qCnt는 현재 퀸의 행
i는 이미 배치된 퀸의 행
visited[qCnt]는 현재 퀸의 열
visited[i]는 이전 퀸의 열

→ 두 퀸의 (행 차이)와 (열 차이)가 같으면 대각선 충돌