[백준] 9663 N-Queen (Java/자바)

 

문제

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

 

문제풀이

처음에는 map을 2차원 배열로 잡고 무지성으로 Brute Force 방법으로 풀었으나 당연하게도 시간초가 났다.

이 문제를 푸는 방법에 대해서는 다른 블로그를 참고하여 풀었는데 그 방법을 보아하니 아래와 같은 로직으로 풀게 되어있었다.

 

(사전지식)

Queen 은 상/하/좌/우/대각선으로 마음대로 움직일 수 있다. 따라서 Queen의 상, 하, 좌, 우 (= 다른 말로 Queen이 놓여진 행/열)의 index와 같은 Queen은 무조건 공격 받는다. 그렇기 때문에 map의 크기를 2차원 배열로 사용하지 않고 1차원 배열로 해놓고 map의 index를 열로, map 안의 원소의 값를 행으로 생각하고 문제를 푼다.

 

1. Queen을 0 열 부터 차례대로 채운다.

2. Queen을 0 행 부터 차례대로 채운다.

3. 이 때, Queen이 해당 열, 행에 채울 수 있는지 검사를 하는데 아래와 같은 조건을 따른다.

  3-1 ) 같은 행에 Queen이 위치하는지 검사한다. ( => map에 같은 원소 값(행)을 갖는다면 false )

  3-2 ) 대각선에 Queen이 위치하는지 검사한다. ( => 열의 차이와 행의 차이가 같을 때 같은 대각선에 놓인다고 본다. )

4. 1~3을 반복하며 N개의 Queen을 갖는다면 count 를 1씩 높여준다.

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static int N, res;
	public static int[] map;
	
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	N = Integer.parseInt(br.readLine());
    	map = new int[N];
    	
    	nQueen(0);
    	
    	System.out.println(res);
    	br.close();
    }
    
    public static void nQueen(int depth) {
    	if(depth == N) {
    		res++;
    		return;
    	}
    	
    	for(int i = 0; i < N; i++) {
    		map[depth] = i;
    		if(isPossible(depth)) {
    			nQueen(depth+1);
    		}
    	}
    }
    
    public static boolean isPossible(int depth) {
    	for(int i = 0; i < depth; i++) {
        	// 같은 행에 Queen이 위치할 때
    		if(map[depth] == map[i]) return false;
    		
    		// 대각선에 Queen이 위치할 때
    		else if(Math.abs(depth-i) == Math.abs(map[depth] - map[i])) return false;
    	}
    	
    	return true;
    }
}

 

참고 블로그

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

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