(코테)백준_9663_N-Queen 백트레킹

 

 

 

 

해결한 답.

import java.util.*;

public class Main {
    static int N;
    static int count = 0;
    static boolean[] col;      // 열 체크
    static boolean[] diag1;    // ↙ 대각선 (row + col)
    static boolean[] diag2;    // ↘ 대각선 (row - col + N - 1)

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 예: 8 입력 시 8-Queen 문제

        col = new boolean[N];
        diag1 = new boolean[2 * N - 1];
        diag2 = new boolean[2 * N - 1];

        solve(0);

        System.out.println(count); // 가능한 정답 개수 출력
    }

    static void solve(int row) {
        if (row == N) {
            count++;
            return;
        }

        for (int c = 0; c < N; c++) {
            if (col[c] || diag1[row + c] || diag2[row - c + N - 1]) continue;

            // 퀸 배치
            col[c] = diag1[row + c] = diag2[row - c + N - 1] = true;

            solve(row + 1); // 다음 행 시도

            // 백트래킹
            col[c] = diag1[row + c] = diag2[row - c + N - 1] = false;
        }
    }
}

 

 

 

 

 

 

 

✅ N-Queen 백트래킹 회고 정리

---

📌 회고

퀸 배치 문제를 처음엔 해설을 보고 겨우 이해했지만,
시간이 좀 지나고(약 일주일 후) 다시 풀어보니 전혀 기억이 나지 않았다.
문제 풀이 로직이 내 것으로 완전히 체화되지 않았다는 걸 느꼈다.

---

❗ 반성할 점

1. 핵심 아이디어를 완벽히 숙달하지 못했다

• N-Queen의 핵심은 **"열과 양 방향 대각선 충돌을 막는 것"**이다.
• 이걸 위해 다음과 같은 boolean 배열을 사용한다:

 

배열 이름	의미	인덱스 계산 방식
col[c]	열 중복 방지	열 인덱스 그대로 사용
diag1[row + col]	↙ 방향 대각선	row + col
diag2[row - col + N - 1]	↘ 방향 대각선	row - col 값 보정해 + N - 1

 

2. 행(row)에 대한 배열이 없는 이유를 처음에 혼동했다

• 하지만 백트래킹 구조에서 row는 항상 0 → N-1로 하나씩만 사용되므로,
• 한 행에 퀸이 하나만 놓이는 구조가 자동 보장됨 → row 체크는 필요 없음

---

✅ 핵심 로직 요약

• solve(row)에서 한 행씩 내려가며 퀸을 한 칸에만 시도
• 열과 대각선이 모두 비어 있으면 퀸을 놓고 row + 1로 재귀 호출
• 가능한 자리가 없거나 끝까지 도달하면 백트래킹을 통해 이전 상태로 되돌아감

---

🧠 느낀 점

• 백트래킹은 "경우의 수를 시도하고, 실패하면 원래대로 되돌아가는" 전략이므로
  각 선택이 상태 변경 → 재귀 → 복구 순서로 이뤄져야 한다.
• 단순히 문제를 푸는 데 성공하는 게 아니라
  구조 자체를 암기 + 이해 + 적용까지 연결되어야 오랫동안 기억된다.