[프로그래머스 Lv.2] N-Queen(Java) - 완전탐색과 가지치기

📌 핵심 요약

• 2차원 배열이 필요 없다 — 행마다 퀸이 하나뿐이므로 queenCol[row] = col 형태의 1차원 배열이면 충분하다
• 행 단위로 재귀를 내려간다 — 같은 행 충돌은 구조적으로 불가능해지고, 확인할 조건이 열과 대각선 둘로 줄어든다
• 대각선은 차이로 판정한다 — 행 차이와 열 차이가 같으면 대각선이며, 절댓값 하나로 두 방향을 함께 처리한다
• 되돌리기 코드가 필요 없다 — 다음 후보가 같은 자리를 덮어쓰고, 검사는 이미 확정된 행만 읽는다

 

목차

1 문제 정리

Programmers #12952

N-Queen

4 ≤ n ≤ 12

난이도: Lv.2

n × n 체스판에 퀸 n개를 서로 공격할 수 없도록 배치하는 경우의 수를 구하는 문제다. 퀸은 가로, 세로, 대각선 방향으로 제한 없이 이동하므로, 두 퀸이 같은 행이나 같은 열에 있거나 대각선상에 놓이면 안 된다.

배치 조건

1. 같은 행에 두 퀸이 있으면 안 된다
2. 같은 열에 두 퀸이 있으면 안 된다
3. 같은 대각선상에 두 퀸이 있으면 안 된다

2 완전탐색의 범위를 좁히기

n이 최대 12이므로 완전탐색으로 접근한다고 판단했다. 다만 무엇을 전부 시도할 것인가에 따라 규모가 크게 달라진다.

접근	후보 개수 (n = 12)	가능 여부
모든 칸에서 12개 고르기	144C12	불가능
행마다 열 하나씩 고르기	1212 ≈ 8.9조	여전히 많음
+ 열 중복 제거	12! ≈ 4.8억	가지치기 필요
+ 대각선 가지치기	실제 탐색은 훨씬 적음	통과

여기서 결정적인 것은 각 행에 퀸이 정확히 하나씩 놓인다는 사실이다. 퀸이 n개이고 행도 n개이며 같은 행에 둘을 놓을 수 없으니, 모든 행이 정확히 하나씩 차지하는 배치만 가능하다.

이 사실을 탐색 구조에 반영하면 “몇 번 행에 놓을까”를 고민할 필요가 사라진다. dfs(row)가 그 행의 열만 정하고 다음 행으로 내려가면 된다.

3 2차원 배열을 쓰지 않은 이유

처음에는 체스판을 그대로 옮겨 boolean[n][n] 형태의 2차원 배열을 만들 생각을 했다.

하지만 행마다 퀸이 하나뿐이므로 1차원 배열 하나로 상태를 전부 표현할 수 있다.

   

example — 1차원 배열로 표현한 배치

// queenCol[row] = 그 행에 놓인 퀸의 열 번호

int[] queenCol = {1, 3, 0, 2};

//      col 0  1  2  3
// 행 0      .  Q  .  .      queenCol[0] = 1
// 행 1      .  .  .  Q      queenCol[1] = 3
// 행 2      Q  .  .  .      queenCol[2] = 0
// 행 3      .  .  Q  .      queenCol[3] = 2

인덱스가 행이고 값이 열이다. 2차원 배열을 쓰면 충돌을 확인할 때마다 격자 전체를 훑어야 하지만, 1차원 배열이면 이미 놓인 행들만 순회하면 된다.

4 충돌 판정

조건	판정 방법
같은 행	확인 불필요 — 행마다 하나씩 놓으므로 구조상 불가능
같은 열	queenCol[i] == col
대각선	Math.abs(queenCol[i] - col) == row - i

대각선 조건이 성립하는 이유

두 점이 대각선상에 있다는 것은 행 차이와 열 차이가 같다는 뜻이다.

기울기가 1 또는 −1인 직선 위에 있다는 것과 같은 말이다.

   

example — row = 3에 놓을 때 (i = 1에 퀸이 있음)

//      col 0  1  2  3
// 행 1      .  Q  .  .      queenCol[1] = 1
// 행 2      .  .  .  .
// 행 3      .  .  ?  ?

// col = 3 → 열 차이 |1 - 3| = 2, 행 차이 3 - 1 = 2  → 대각선 충돌
// col = 2 → 열 차이 |1 - 2| = 1, 행 차이 3 - 1 = 2  → 안전

열 차이에만 절댓값을 씌우는 이유는 두 대각선 방향을 한 번에 처리하기 위해서다. 반면 행 차이 row - i는 i < row이므로 항상 양수라 절댓값이 필요 없다.

5 전체 코드

   

Java — Solution.java

class Solution {
    private int[] queenCol;   // queenCol[row] = 그 행에 놓인 퀸의 열
    private int n;
    private int answer;

    public int solution(int n) {
        this.queenCol = new int[n];
        this.n = n;
        this.answer = 0;

        setQueen(0);

        return answer;
    }

    // row행에 퀸을 놓는다
    private void setQueen(int row) {
        // 모든 행에 놓았으면 배치 하나가 완성된 것
        if (row == n) {
            answer++;
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                queenCol[row] = col;
                setQueen(row + 1);
            }
        }
    }

    // (row, col)에 퀸을 놓을 수 있는지 확인
    private boolean isSafe(int row, int col) {
        for (int i = 0; i < row; i++) {
            // 같은 열
            if (queenCol[i] == col) {
                return false;
            }
            // 대각선 — 행 차이와 열 차이가 같으면 대각선
            if (Math.abs(queenCol[i] - col) == row - i) {
                return false;
            }
        }
        return true;
    }
}

6 되돌리기 코드가 없는 이유

백트래킹이라고 하면 보통 선택 → 탐색 → 되돌리기 세 단계를 떠올린다.

그런데 이 코드에는 queenCol[row] = col 뒤에 원복하는 줄이 없다.

   

비교 — 되돌리기가 필요한 경우와 아닌 경우

// 되돌리기가 필요한 형태 (공유 컬렉션에 누적)
currentKey.add(i);
dfs(...);
currentKey.remove(i);   // 빠뜨리면 상태가 오염된다

// 되돌리기가 불필요한 형태 (인덱스에 덮어쓰기)
queenCol[row] = col;
setQueen(row + 1);
// 다음 col이 같은 자리를 덮어쓴다

두 가지 이유가 겹친다. 첫째로 다음 col 후보가 같은 인덱스를 덮어쓰므로 잔재가 남지 않는다. 둘째로 isSafe가 i < row 범위만 읽으므로, 아직 확정되지 않은 행의 값은 애초에 참조되지 않는다.

💡

상태를 어떻게 담는가가 되돌리기 여부를 결정한다

컬렉션에 원소를 쌓아 올리는 구조라면 되돌려야 하고, 고정 크기 배열의 정해진 자리에 덮어쓰는 구조라면 되돌릴 필요가 없다. 자료구조 선택이 실수 가능성 자체를 줄여준다.

7 정리

항목	내용
자료구조	int[n] 하나 — 인덱스는 행, 값은 열
탐색 단위	행 — setQueen(row)가 그 행의 열만 결정
확인할 조건	열 일치, 대각선 — 같은 행은 구조상 불가능
가지치기	isSafe가 false면 그 아래 가지를 전부 차단
공간 복잡도	O(n) — 2차원 배열 대비 크게 절약

이 문제에서 얻은 것은 문제의 제약을 자료구조에 미리 반영하면 확인할 조건이 줄어든다는 점이다.

“행마다 퀸이 하나”라는 사실을 배열 구조에 담아두면 같은 행 충돌은 검사할 필요조차 없어진다.

체스판이니 2차원 배열이라는 생각이 자연스럽지만, 실제로 저장해야 할 정보가 무엇인지 따져보면 1차원으로 충분한 경우가 많다고 판단했다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.