[伯俊]#9663 N-Queen-JAVA

問題の条件と説明

にゅうしゅつりょく

アイデア

に答える

int型配列(array)を宣言した後、配列のインデックス(depth)をチェス盤の列に設定し、インデックスの値(i)をチェス盤の行に設定します。 行と列が配置可能な場所にある場合はindex(depth)を増やし、再帰呼び出しを行います。 配置可能な場所の決定方法 列の前の列と同じ行ではなく、繰り返し文を使用する場合、行と列の前の行と列の間の減算値が異なる場合は、行と列に配置できます。 最後の行の再帰に進むと、カウントが増加し、再帰が終了します。

ソースコード

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;
	}
}