첫째 줄에 N이 주어진다. (1 ≤ N < 15)
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
이 문제를 풀기전에 제일 먼저 알아야하는 것은
퀸은 왼쪽, 오른쪽, 위, 아래, 대각선으로 이동이 가능하다는 것
즉, 퀸의 위치에서 위의 위치들을 재귀적으로 확인해야한다.
같은 행 또는 열에 위치하는지, 대각선에 위치하는지를 확인하는 check
함수와
재귀적으로 파악하는 nQueen
함수로 코드를 구성
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, cnt = 0;
static int[] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
map = new int[N];
nQueen(0);
System.out.println(cnt);
}
static void nQueen(int depth) {
if (depth == N) {
cnt++;
} else {
for (int i = 0; i < N; i++) {
map[depth] = i;
// 이동 가능 여부를 파악하여 백트랙킹 기법 사용
// 재귀호출 사용
if (check(depth)) {
nQueen(depth + 1);
}
}
}
}
static boolean check(int depth) {
for (int i = 0; i < depth; i++) {
// 같은 행에 존재하는지
if (map[i] == map[depth]) {
return false;
}
// 대각선에 존재하는지
if (Math.abs(i - depth) == Math.abs(map[i] - map[depth])) {
return false;
}
}
return true;
}
}