백준 9663번, N-Queen : Java

🔗 문제 링크

N-Queen

 

🔎 문제 풀이

백준 'N과 M' 4문제를 통해 백트래킹 원리를 조금 이해하게 되었고 ,, 그 유명한 (?) N-Queen 문제를 도전했다.

 

퀸은 가로, 세로, 대각선으로 이동할 수 있다.

즉, 퀸을 서로 공격할 수 없게 놓기 위해서는 퀸 위치의 가로, 세로, 대각선에 또 다른 퀸이 존재하면 안 된다는 것이다.

 

퀸 위치 좌표는 배열을 통해 저장한다.

처음에는 x, y 좌표가 떠올라 2차원 배열로 놓았는데

풀다가 어려워서 찾아보니 1차원 배열로 해결하더라 ,,!

나 빼고 다 천재가 틀림이 없다 ,,

배열의 index를 열로 두고, 해당 index의 값을 행으로 두면 되는 것이다 ,,,! 

그럼 같은 행에 위치하거나 대각선에 위치하는지에 대해서만 검사하면 된다.

 

퀸을 놓을 수 있다면 depth에 1을 증가시켜 재귀 함수를 호출시키고,

depth == N이라면 문제 조건에 맞는 경우의 수를 찾은 것이므로 count를 1 증가한다.

그리고 count를 출력하면 된다.

 

 

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
        
public class Main {
	static int N;
	static int[] queenPlace;
	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());
    	queenPlace = new int[N];
    	findNQueen(0);	
    	System.out.println(count);
    }
    
	
    public static void findNQueen(int depth) {
    	if (depth == N) {
    		count++;
    		return;
    	}
    	
    	for (int i = 0; i < N; i++) {
    		queenPlace[depth] = i;
    		
    		if (getPossibillity(depth)) {
        		findNQueen(depth+1);
        	}
    	}
   
    }
    
    public static boolean getPossibillity(int column) {
    	for (int i = 0; i < column; i++) {
    		if (queenPlace[column] == queenPlace[i])
    			return false;
    		
    		if (Math.abs(column - i) == Math.abs(queenPlace[column] - queenPlace[i]))
    			return false;
    	}
    	
    	return true;
    }
}

 

---

Reference

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