해당 행과 열에 퀸을 놓은 후 다음 행과 열에 놓을 수 있는 지 판단하여 놓을 수 없을 경우 다시 되돌아 가는 "백트래킹" 과정을 이용한다.
int형 배열(array)을 선언 한 후, 배열의 index(depth)를 체스판의 열로 해당 index의 값(i)을 체스판의 행으로 설정한다.
해당 행과 열이 놓을 수 있는 위치라면 index(depth)를 증가시키며 재귀 호출을 한다.
마지막 행까지 재귀를 진행했을 경우 경우의 수(count)를 증가시킨 후, 리턴하여 재귀를 마무리한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static int array[];
public static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
array = new int[N];
count = 0;
n_Queen(N, 0);
System.out.println(count);
}
public static void n_Queen(int N, int depth) {
// 재귀 깊이가 N과 같아지면 경우의 수 증가
if(depth == N) {
count++;
return;
}
for(int i=0; i<N; i++) {
array[depth] = i;
// 해당 행과 열에 놓을 수 있을 지 판단
if(possibility(depth)) {
array[depth] = i; // 해당 깊이를 index(열)로 하여 i(행) 값 저장
n_Queen(N, depth+1); // 다음 자식 노드 방문을 위해 depth 1 증가시킴
}
}
}
public static boolean possibility(int depth) {
for(int i=0; i<depth; i++) {
// 같은 행이라면
if(array[i] == array[depth])
return false;
// 대각선 위치라면 (행끼리 뺀것과 열끼리 뺀것이 같으면 대각선 위치)
else if(Math.abs(array[i]-array[depth]) == Math.abs(i-depth))
return false;
}
return true;
}
}