출처: https://www.acmicpc.net/problem/9663
N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력 형식
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력 형식
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제 입력 1
8
예제 출력 1
92
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
System.out.println(solveNQueens(N));
}
public static int solveNQueens(int n) {
boolean[] cols = new boolean[n]; // 열에 퀸 유/무
boolean[] diag1 = new boolean[2 * n - 1]; // 왼쪽 아래 대각선의 퀸 유/무
boolean[] diag2 = new boolean[2 * n - 1]; // 오른쪽 아래 대각선의 퀸 유/무
return dfs(0, n, cols, diag1, diag2);
}
private static int dfs(int row, int n, boolean[] cols, boolean[] diag1, boolean[] diag2) {
if (row == n) {
return 1;
}
int count = 0;
for (int col = 0; col < n; col++) {
// 세로열의 퀸 존재, 왼쪽 아래 대각선의 퀸, 오른쪽 아래 대각선의 퀸 체크
if (!cols[col] && !diag1[____] && !diag2[____]) {
cols[col] = diag1[row + col] = diag2[row - col + n - 1] = true;
// 다음 행에 대한 탐색
count += ____;
cols[col] = diag1[row + col] = diag2[row - col + n - 1] = false;
}
}
return count;
}
}
빈칸1: X
정답: row + col
해설: 왼쪽 아래 대각선은 모든 칸에서 row + col 값이 동일합니다. 따라서 diag1[row + col]을 사용하여 퀸의 위치를 추적합니다. 다른 보기는 대각선 방향과 무관하거나 불필요한 값을 포함합니다.
->나는 row-col+n-1을 선택함 왼쪽이니 - col을 해야 하고 대각선 아래이니 n-1을 해야 한다 생각했다.
빈칸2: X
정답: row - col + n - 1
해설: 오른쪽 아래 대각선은 모든 칸에서 row - col 값이 동일합니다. 음수 값을 피하기 위해 row - col + n - 1으로 보정하여 배열의 유효한 인덱스를 만듭니다. 다른 보기는 음수 인덱스가 될 위험이 있거나 잘못된 방향입니다.
->나는 row+col+n-1을 선택함 오른쪽이니 + col을 대각선 아래이니 n-1이라고 생각했다.
빈칸3: O
정답: dfs(row + 1, n, cols, diag1, diag2)
해설: 현재 행(row)에서 유효한 퀸의 위치를 찾았다면, 다음 행(row + 1)으로 이동하여 탐색을 계속해야 합니다. 다른 선택지는 백트래킹 구조를 방해하거나 잘못된 인덱스를 참조합니다.
