[BOJ]9663_Nqueen_Java

--문제--

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

9663번: N-Queen

--문제 접근--

Nqueen은 대표적인 백트래킹 문제로서 DFS에서 조건을 추가해주는 과정입니다.

가지치기를 잘해주면 되는 문제이다.

체스판에 퀸을 놓기전에 그자리에 놓을수 있는 자리인지 확인하는 과정을 추가하면서 놓아주면 문제가 해결됩니다.

package Class4;

import java.util.Scanner;

public class Nqueen {
	static boolean[][] map;
	static int N,count;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
			N=sc.nextInt();
			map=new boolean[N][N];
			count=0;
			dfs(0);
			System.out.println(count);
	}
	static void dfs(int cnt) {
		if(cnt==N) {
			count++;
			return;
		}
		
		for(int i=0;i<N;i++) {
			if(isable(cnt,i)) {//놓을수 있는 자리인지 확인하는과정
				map[cnt][i]=true;
				dfs(cnt+1);
				map[cnt][i]=false;
			}
		}
	}
	private static boolean isable(int cnt, int x) {
		for(int i=0;i<cnt;i++) {
			if(map[i][x]==true)return false;
		}
		for(int i=cnt,j=x;i>=0&&j>=0;i--,j--) {
			if(map[i][j]==true)return false;
		}
		for(int i=cnt,j=x;i>=0&&j<N;i--,j++) {
			if(map[i][j]==true)return false;
		}
		return true;
	}
}