기타/코딩테스트
(코테)백준_9663_N-Queen 백트레킹
불광동 물주먹
2025. 5. 12. 16:23

해결한 답.
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로 재귀 호출
- 가능한 자리가 없거나 끝까지 도달하면 백트래킹을 통해 이전 상태로 되돌아감
🧠 느낀 점
- 백트래킹은 "경우의 수를 시도하고, 실패하면 원래대로 되돌아가는" 전략이므로
각 선택이 상태 변경 → 재귀 → 복구 순서로 이뤄져야 한다. - 단순히 문제를 푸는 데 성공하는 게 아니라
구조 자체를 암기 + 이해 + 적용까지 연결되어야 오랫동안 기억된다.