[백준] #9663 N-Queen - JAVA

문제 조건 및 설명

• N-Queen 문제란 크기가 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없도록 놓는 경우의 수를 구하는 문제이다.
• "서로 공격할 수 없다"의 조건 : 퀸이 놓였을 때 퀸 자신을 기준으로 일직선상(가로 및 세로)과 대각선 방향에는 아무것도 놓여있으면 안 된다.

입출력

아이디어

• 해당 행과 열에 퀸을 놓은 후 다음 행과 열에 놓을 수 있는 지 판단하여 놓을 수 없을 경우 다시 되돌아 가는 "백트래킹" 과정을 이용한다.

  • 백트래킹 : 어떤 노드의 '유망성'을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가 다른 자식노드를 찾는다.

풀이

• int형 배열(array)을 선언 한 후, 배열의 index(depth)를 체스판의 열로 해당 index의 값(i)을 체스판의 행으로 설정한다.

• 해당 행과 열이 놓을 수 있는 위치라면 index(depth)를 증가시키며 재귀 호출을 한다.

  • 놓을 수 있는 위치인 지 판단 방법
    반복문을 사용하여 해당 열 이전의 열과 같은 행이 아닐 경우, 해당 행과 열 이전의 행과 열끼리 뺄셈한 값이 같지 않을 경우 해당 행과 열에 놓을 수 있다.

• 마지막 행까지 재귀를 진행했을 경우 경우의 수(count)를 증가시킨 후, 리턴하여 재귀를 마무리한다.

---

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
	
	public static int array[];
    public static int count;
    
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		array = new int[N];
		count = 0;
		n_Queen(N, 0);
		System.out.println(count);
		
	}
	
	public static void n_Queen(int N, int depth) {
		
		// 재귀 깊이가 N과 같아지면 경우의 수 증가
		if(depth == N) {
			count++;
			return;
		}
		
		for(int i=0; i<N; i++) {
			array[depth] = i;
			// 해당 행과 열에 놓을 수 있을 지 판단
			if(possibility(depth)) {
				array[depth] = i; // 해당 깊이를 index(열)로 하여 i(행) 값 저장
				n_Queen(N, depth+1); // 다음 자식 노드 방문을 위해 depth 1 증가시킴
			}
		}
	}
	
	public static boolean possibility(int depth) {
		for(int i=0; i<depth; i++) {
			// 같은 행이라면
			if(array[i] == array[depth])
				return false;
			// 대각선 위치라면 (행끼리 뺀것과 열끼리 뺀것이 같으면 대각선 위치)
			else if(Math.abs(array[i]-array[depth]) == Math.abs(i-depth))
				return false;
		}
		return true;
	}
}