[백준] 9663 N-Queen

9663번: N-Queen (acmicpc.net)

9663번: N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

 

내 풀이

 

처음 이 문제를 접했을 때는 N * N 배열에서 되는 곳과 아닌곳을 체크해나가면서 해결하였었지만 비효율적이였다. 그 당시에 배웠던 다른 방법으로 다시 풀어본 내용이다 복습한 내용

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

public class Main {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static String src = "4";
		
	static int N,result;
	static int[] col;
	
	public static void main(String args[]) throws IOException {
		//input= new BufferedReader(new InputStreamReader(System.in));
		input = new BufferedReader(new StringReader(src));
		
		N= Integer.parseInt(input.readLine());
		result=0;
		col=new int[N];
		
		sol(0);
		System.out.println(result);
	}
	
	public static void sol(int depth) {
		if(depth==N) {
			result++;
			return;
		}else {
			
			for(int i=0;i<N;i++) { 
				//System.out.println(Arrays.toString(col));
				col[depth]=i; //일단 배치해봄
				if(isPossible(depth)) {// 배치가 유효한지 검사
					sol(depth+1); //다음 행 진행
				}else { // 아닌 경우 초기화
					col[depth]=0;
				}
			}
		}
				
	}
	
	public static boolean isPossible(int depth) {
		
		for(int i=0;i<depth;i++) { //더 위에 있는 퀸에 잡히는지 검사                                     
			//세로 줄에 걸리는경우 || 대각선
			if(col[depth]==col[i]||Math.abs(col[depth]-col[i])==depth-i){ 
				return false;
			}
		}
		return true;
	}
	
	
}