N-Queen

문제

https://www.acmicpc.net/problem/9663

해설

// arr[]={0,3,1,2}이면 // 값은 열을 뜻하고 인덱스는 행을 뜻함.
// 0 1 2 3
//0
//1
//2
//3

dfs와 다르게 끝까지 탐색하는게 아니라 조건에 맞지않으면 뒤로 갔다가 재귀호출을 함

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class B9663 {
 
	public static int[] arr;
	public static int N;
	public static int count = 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(count);
 
	}
 
	public static void nQueen(int depth) {
		
		if (depth == N) {
			count++;
			return;
		}
 
		for (int i = 0; i < N; i++) {
			arr[depth] = i;
			
			if (Possibility(depth)) {
				nQueen(depth + 1);
			}
		}
		
		
	}
 
	public static boolean Possibility(int col) {
 
		for (int i = 0; i < col; i++) {
			// 같은 행에 존재할 경우
			if (arr[col] == arr[i]) {
				return false;
			} 
			
			/*
			 * 대각선상에 놓여있는 경우
			 * 열의 차와 행의 차가 같을 경우가 대각선에 놓여있는 경우다
			 */
			else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
				return false;
			}
		}
		
		return true;
	}
}