[백준_9663번] N-Queen

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

9663번: N-Queen

[문제]

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

[코드]

import java.util.*;

public class BaekJoon_9663 {
	/*
	 * chess 배열의 인덱스를 열, 원소 값을 행이라고 생각한다면
	 * 2차원 배열이 아닌 1차원 배열을 사용하여 문제 해결 가능 
	 */
	public static int[] chess;
	public static int n, count=0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		chess=new int[n];
		
		nQueen(0);
		System.out.println(count);
	}	
	public static void nQueen(int depth) {
		// n*n 체스판에 n개의 퀸을 모두 놓을수 있는 경우의 수를 찾았을때 count 증가
		if(depth==n) {
			count++;
			return;
		}
		// n*n 체스판의 각 열에 퀸을 배치할 수 있는지 검사
		for(int i=0;i<n;i++) {
			// 해당 열의 i번째 행에 퀸 배치
			chess[depth]=i;
			// 배치가 가능하면 다음 열로 넘어간다.
			if(Possibility(depth)) {
				nQueen(depth+1);
			}
		}
	}
	
	public static boolean Possibility(int col) {
		for(int i=0;i<col;i++) {
			// 퀸이 같은 행에 존재할 경우는 불가능
			if(chess[col]==chess[i])
				return false;
			/*
			 * 퀸은 대각선상에 위치 불가
			 * = 열의 차와 행의 차가 같은 경우가 대각선에 놓여있는 경우 
			 */
			else if (Math.abs(col - i) == Math.abs(chess[col] - chess[i])) {
				return false;
			}
		}
		return true;
	}
}

 

[고찰]

 이번 문제는 앞선 백트래킹 문제인 N과 M보다는 더 어려운 문제였다. 같은 열과 대각선 상에는 위치할 수 없는 n개의 퀸을 n*n의 체스판 위에 배치할 수 있는 경우의 수를 출력하는 문제인데, 나는 행과 열을 저장하기 위해 2차원 배열을 사용하려 했다. 하지만 다른 사람들의 코드를 참고하니 인덱스를 열, 원소 값을 행으로 하여 1차원 배열로 간소화 할 수 있다는 것을 알았다. 가장 어려웠던 점은 퀸을 대각선에 놓지 않게하기 위해 조건을 거는 부분을 구현하기가 어려웠다. 이러한 문제는 다른 분들의 코드를 참고하여 해결하였지만 스스로 고민해보는 시간을 좀 더 투자해야 할 것 같다.