2016년 7월 25일 월요일

dfs 알고리즘 : NQueen


package N_Queen;

import java.util.Scanner;

public class source {
static int n;
static int arr[][] = new int[15][15];
static boolean chk[] = new boolean[15];
public static void main(String[] args){

Scanner sc = new Scanner(System.in);
n = sc.nextInt();
System.out.println(back(1));
}
static int back(int k){
if (k==n+1) return 1;
int total=0;
for (int i=1;i<=n; i++){
if(chk[i]) continue;
boolean impossible = false;
for(int j=1; j<k; j++){
if (i-j>0 && arr[k-j][i-j]==1) impossible = true;
if (i+j<=n && arr[k-j][i+j]==1) impossible = true;
}
if(impossible) continue;
arr[k][i] = 1;
chk[i] = true;
total += back(k+1);
arr[k][i] = 0;
chk[i] = false;
}
return total;
}
}

댓글 없음:

댓글 쓰기