[백준 / C++] 9663번 N-Queen

문제 재정의 및 추상화

결론: N x N 판에 퀸 N개를 둘 수 있는 경우의 수를 구하라

문제 접근 방식

• 체스판은 행, 열로 이루어져 있다. → 2차원 배열을 써보자.
• 퀸은 가로-세로-대각선 방향을 공격할 수 있다.
  → 행-열에는 하나의 퀸만 존재할 수 있다.
  → 다른 퀸과 행 번호와 열 번호의 차이값이 같으면 같은 대각선 상에 위치하므로 안 된다.
• 배열의 특정 위치에 퀸을 놓아보면서 진행하다가 더 이상 안되면 탐색을 멈추고 되돌아가서 다른 자리로 이동한다.

해법을 찾는데 결정적이었던 깨달음

📌 int arr[행] = [열] 로 생각하기

행, 열이라는 개념 때문에 자연스럽게 2차원 배열로 생각했지만, 이 문제는 1차원 배열로 충분히 풀이가 가능하다.
어차피 한 행에 퀸은 하나밖에 들어가지 못하기 때문에, 몇 번째 행에는 몇 번째 열이 가능하다를 표현하면 된다.

즉, 인덱스는 행이고, 배열 값은 열이다.

문제 풀이 로직

1. 같은 행에 1개의 퀸만 가능하다는 전제로 0번 행부터 탐색 시작
2. 총 n개의 루프를 돌면서(n개의 열 탐색) 해당 위치에 퀸을 둬도 되는지 검사 → 함수 이용
3. 함수에서는 현재 행까지 루프를 돌면서 이전에 둔 퀸이 공격 가능한지 검사 → 두 조건 고려
4. 함수에서 퀸을 둘 수 있는 위치에 해당하는 열을 발견하면 다음 행으로 넘어감
   4-1. 없다면 이전으로 되돌아감
5. 반복
6. 만약 이번 행이 마지막 행(n번째 행)이라면 n개의 퀸을 놓은 것이므로 count++

문제 풀이

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

int board[15];
int n, cnt = 0;

int checkCondition(int row) {
    for (int i = 0; i < row; i++) { // 상위 행들에 대해 반복
        // 현재 행의 열 == 상위 행의 열 (같은 열에 있는 경우) 혹은 현재 행 - 상위 행 == 현재 열 - 상위 열(같은 대각선상에 있는 경우) 이면
        if (board[row] == board[i] || row - i == abs(board[row] - board[i])) {
            return 0; // row 행에 col번째 열은 불가능. 다시 돌아간다.
        }
    }
    return 1; // for문을 무사히 통과했다면 이 행은 통과
}

void nQueen(int row) {
    if (row == n) { // 모든 행을 다 통과했다면
        cnt++; // 횟수 하나 세기
        return;
    }

    for (int col = 0; col < n; col++) {
        board[row] = col; // row 행에 col번째 열을 넣어보고
        if (checkCondition(row)) { // 이 행에서 가능한지 검사
            nQueen(row + 1); // 가능하면 다음 행으로 넘어감
        }
    }
}

int main() {
    cin >> n;
    nQueen(0);
    cout << cnt;
    return 0;
}