[BOJ] 9663번 : N-Queen
접근 방법
체스판의 최대 크기가 15×15이므로 퀸을 놓는 모든 경우의 수는 225 C 15가 됩니다. 225 C 15의 결과는 약 9×10^22이므로 모든 퀸을 놓고 서로 공격 가능한지 검사하는 것으로는 해결할 수 없습니다. 그래서 퀸을 놓을 때마다 이전에 놓은 퀸들과 서로 공격이 가능한지 검사하는 방식으로 문제를 해결해야 합니다. 퀸들이 서로 상하좌우 방향으로 공격이 가능한지 검사를 하는 방법은 서로 같은 행 혹은 같은 열에 있는지 검사를 하면 쉽게 알 수 있습니다. 대각선 방향으로 서로 공격이 가능한지는 아래의 방법으로 검사가 가능합니다.
행 번호와 열 번호를 서로 더했을 경우 우측상단에서 좌측하단으로 향하는 대각선의 방향의 수들이 서로 같음을 볼 수 있습니다.
행 번호에서 열 번호를 뺄 경우 좌측상단에서 우측하단으로 향하는 대각선의 방향의 수들이 서로 같음을 볼 수 있습니다.
위 두가지 방법을 이용하여 서로 퀸들이 대각선 방향으로 공격이 가능한지 검사할 수 있습니다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int[] columns;
static int count = 0;
public static void main (String[] args) {
input();
func(0);
System.out.println(count);
}
static void input() {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
columns = new int[n];
scanner.close();
}
// rec은 퀸을 놓을 행의 번호
static void func(int rec) {
// 모든 퀸을 서로 공격 불가한 위치에 놓았을 경우
if (rec == n) {
++count;
return;
}
// i는 퀸을 놓을 열의 번호
for (int i = 0; i < n; ++i) {
boolean placable = true;
// 이전에 놓은 퀸들과 공격 가능한지 검사한다.
for (int j = 0; j < rec; ++j) {
// 서로 공격 가능할 경우
if (attackable(j, columns[j], rec, i)) {
placable = false;
break;
}
}
// rec, i 위치에 놓을 수 있을 경우
if (placable) {
columns[rec] = i;
func(rec + 1); // 다음 행에 대해
}
}
}
// 두 위치의 퀸이 서로 공격 가능한지 검사하는 함수
static boolean attackable(int row1, int col1, int row2, int col2) {
if (col1 == col2) return true;
// 우측상단에서 좌측하단으로 그은 대각선에 위치했는지
if (row1 + col1 == row2 + col2) return true;
// 좌측상단에서 우측하단으로 그은 대각선에 위치했는지
if (row1 - col1 == row2 - col2) return true;
// 서로 공격 불가
return false;
}
}
Author And Source
이 문제에 관하여([BOJ] 9663번 : N-Queen), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@errored_pasta/BOJ-9663번-N-Queen저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)