9663 N-Queen

 

---

https://st-lab.tistory.com/118

[백준] 9663번 : N-Queen - JAVA [자바]

 

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int[] arr;
	static int cnt = 0;
 public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	N = Integer.parseInt(br.readLine());
	arr = new int[N];
	NQueen(0);
	System.out.println(cnt);
 }
 static void NQueen(int depth) {
	 if(depth == N) {
		 cnt++;
		 return;
	 }
	 
	 for(int i = 0; i < N; i++) {
		 arr[depth] = i; //i는 열, depth는 행이다 arr[0] = 0으로 재귀함수를 시작
		 if(possibility(depth)) {
			 NQueen(depth + 1);
		 }
	 }
 }
 static boolean possibility(int row) {
	 for (int i = 0; i < row; i++) {
		 if(arr[row] == arr[i]) { //row가 0일땐 반복문이 실행되지 않음
			 return false;
		 }
		 else if(Math.abs(row - i) == Math.abs(arr[row] - arr[i])) { //열의 차가 같을 경우 대각선이다. row는 행이고 arr[row]는 열이다.
			 //-i 는 전의 행을 의미한다 -arr[i]는  전의 열을 의미한다
			 return false;
		 }
	 }
	 return true;
 }
}