n=2 라고 가정했을 때, 2*2 행렬에서 2개의 퀸이 배치될 수 있는 모든 수를 구하는 문제이다.
전체적으로 n만큼 반복하고, 재귀적으로 다시 n만큼 돌면서 퀸이 배치될 수 있는 모든 경우의 수를 체크한다.
import java.util.Scanner;
public class Main2 {
static int n;
static int QueenCnt = 0;
// 3가지 상태 확인
// 1.같은 열에 있는지
// 2.좌측하단 우측상단 대각선
// 3.좌측상단 우측하단 대각선
// ** 수학적으로 규칙을 판단할 필요 **
// 대각선에서 필요한 배열 칸의 개수 1=1, 2=3, 3=5 -> 2n-1 -> 문제에서 n의 최대 개수가 14이므로 크기를 최소 27로 설정해야 함
static boolean[] isUsed1 = new boolean[27];
static boolean[] isUsed2 = new boolean[27];
static boolean[] isUsed3 = new boolean[27];
public static void func(int k) {
// k(퀸)이 n개가 모두 놓였을 경우 QueenCnt(배치 개수 증가)
// n개가 모두 놓이지 못하면 무한루프에 빠지는 것이 아닌가? -> 퀸이 놓이지 못하면 조건문에서 continue로 빠져나가므로 재귀적으로 함수를 호출하지 않음
if(k == n) {
QueenCnt++;
return;
}
// n만큼 반복하면서 퀸이 놓일 수 있는 위치 체크
for(int i=0;i<n;i++) {
/*
isUsed2 인덱스 구성하는 법)
2*2 행렬에서
[0][1], [1][0]은 동일한 대각선에 있다.
"행+열"의 결과값이 동일하면 그 좌표는 모두 동일한 대각선에 있음을 알 수 있다.
isUsed3 인덱스 구성하는 법)
2*2 행렬에서
[0][0], [1][1]은 동일한 대각선에 있다.
"행 - 열"의 결과값이 동일하면 그 좌표는 모두 동일한 대각선에 있음을 알 수 있다.
좌측 상단에서 우측 하단으로 생긴 모든 대각선은 총 3개로 다음과 같다.
[0][1] = 0-1 = -1
[0][0], [1][1] = 0
[1][0] = 1-0 = 1
"행 - 열"의 결과값을 인덱스로 해서 각 인덱스는 대각선을 의미하도록 한다.
그러나 -1라는 음수의 결과가 생기므로 최소 0이 되도록 변경해야 한다.
2*2 행렬에서 k-i를 했을 때 나오는 최소값이 -1이므로 0으로 변경하기 위해서 1을 더해야 한다.
그러나 1은 2*2 행렬에만 해당하는 고정값이기 때문에 "n-1"을 더함으로써 다른 행렬에도 똑같이 적용이 가능하다.
"n-1"을 더하면 모든 인덱스가 1씩 늘어나기 때문에 인덱스 별로 각 대각선을 의미하게 된다.
[0][1] = 0-1 = -1 + (n-1) = 0
[0][0], [1][1] = 0 + (n-1) = 1
[1][0] = 1-0 = 1 + (n-1) = 2
*/
if(isUsed1[i] || isUsed2[k+i] || isUsed3[k-i+n-1]) continue;
isUsed1[i] = true;
isUsed2[k+i] = true;
isUsed3[k-i+n-1] = true;
func(k+1); // 퀸이 놓이지 못하면 재귀적으로 함수가 호출되지 않음
isUsed1[i] = false;
isUsed2[k+i] = false;
isUsed3[k-i+n-1] = false;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
func(0);
System.out.println(QueenCnt);
}
}