こんにちは！グンです。
今回は有名なアルゴリズム問題である
N-Queenです。
안녕하세요! 근입니다.
이번에는 유명한 알고리즘 문제인
N-Queen입니다.
ソース(출처)：https://www.acmicpc.net/problem/9663
問題 / 문제
N x Nのチェス盤の上にクイーンN個をお互い攻撃出来ないようにおく問題です。
Nが与えられた場合、クイーンを置く方法の数を出すプログラムを作成して下さい。
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
入力 / 입력
最初のラインにNが与えられる。(1 ≤ N < 15)
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
出力 / 출력
最初のラインにお互い攻撃出来ない場合の数を出力する。
첫째 줄에 서로 공격할 수 없는 경우의 수를 출력한다.
例 / 예시
| 番号 / 번호 | 入力 / 입력 | 出力 / 출력 |
|---|---|---|
| 1 | ８ | 92 |
私の考え / 나의 생각
N x Nのチェス盤の最初の行から最後の行までクイーンを置いてみる。
置けない場合は以前のクイーンの位置を変える。
最後の行まで辿り着いたならカウントを増加させる。
最初の行の検査がNに行くまで繰り返す。
N x N의 체스판의 처음 행에서 마지막 행까지 퀸을 놓아본다.
놓을 수 없는 경우는 이전의 퀸 위치를 바꾼다.
마지막 행까지 도닥하면 카운드를 증가시킨다.
마지막 행의 검사가 N까지 갈 때까지 반복한다.
コード
import java.util.Scanner;
class Main {
static int count = 0;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // 1)
int[] col = new int[n];
for(int i=0;i<n;i++) { // 2)
col[0] = i;
nqueen(0,col);
}
System.out.println(count); // 5)
input.close();
}
public static boolean rule(int index, int col[]) { // 4)
int k = 0;
boolean swit = true;
while(k < index && swit) {
if(col[k] == col[index] || Math.abs(col[k] - col[index]) == index - k) {
swit = false;
}
k++;
}
return swit;
}
public static void nqueen(int index, int[] col) { // 3)
if(rule(index,col)) {
if(index == col.length-1) {
count++;
}
else {
for(int i=0;i<col.length;i++) {
col[index + 1] = i;
nqueen(index+1,col);
}
}
}
}
}
1)
Nの入力を貰って、Nの大きさの配列を宣言する。各配列の値は、対応する行内の列の位置を意味します。
N의 입력을 받고, N 크기의 배열을 선언한다. 각 배열의 값은 해당하는 행의 열의 위치를 의미한다.
2)
最初の行に対応する配列のIndexに位置の情報をNまで更新しながらnqueen関数をよぶ。
첫째 열에 해당하는 배열의 인덱스에 위치 정보를 N까지 갱신하면서 nqueen함수를 부른다.
3)
クイーンを置けるルールを検査する。
置ける位置の場合、現在の行がNの場合カウントを増加するし、Nじゃなかったら次の行に位置を書いて同じことを繰り返す。
퀸을 놓을 수 있는 규칙을 검사한다.
놓을 수 있는 위치일 경우, 현재 행이 N일 경우 카운트를 증가시키고, N이 아닐 경우 다음 행에 위치를 적고 같은 것을 반복한다.
4)
検査しようとしている行の以前の行を全部検査する。
直線上の位置と対角線上の位置に配置できないため、その線の上に置こうとしている場合はfalseをreturnする。
검사하려고 하는 행의 이전의 행을 전부 검사한다.
직선 위의 위치와 대각선 위의 위치에 배치할 수 없기 때문에, 그 선 위에 놓으려고 하는 경우는 false를 리턴한다.
