Baekjoon9663: N-Queen

N-Queen

10 초

128 MB

50440

25920

16972

50.773%

문제

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

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

입력

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

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

풀이

백트래킹의 대표 문제 중 하나라고 한다. N-Queen에 규칙에 의해 NxN 체스판에 N개의 퀸을 놓기 위해서는 각 줄에 하나씩 퀸을 놓아야만 한다. 즉 첫째줄이든, 둘째줄이든 퀸은 무조건 존재한다는 뜻이다. 이 규칙에 의해 첫째줄에 퀸은 무조건 놓일 수 밖에 없으므로 첫째줄(1행)에 퀸이 어느 자리(열)에 오는지에 따라 다음 줄에 퀸이 놓일 수 있는지 탐색해본다.

퀸의 자리 배치 규칙

퀸의 공격 방향은 가로줄과 세로줄 모두와 대각선 경로 모두이다. 만약 퀸의 위치가 (row, column)이라고 하면 다음과 같다.

가로줄 공격 방향: (row, N보다 작은 모든 수) 세로줄 공격 방향: (N보다 작은 모든 수, column) 대각선: (a, b)에 대해 ( |row-a| = |column-b| )를 만족하는 a와 b 좌표

대각선식을 조금 고민했었는데 2차원 배열에서 반복문을 통해 4가지 방향으로 (오른쪽 위/아래 대각, 왼쪽 위/아래 대각) 배열에 표시하는 방법을 구상해보았지만 너무 비효율적이라고 판단했다. 그래서 좌표를 뺐을 때 +4, -4 처럼 좌표 차이의 절대값 크기가 같아 졌을 때 대각선으로 판별하도록 했고 위 세가지 조건에 들어가지 않는 자리에 다음 퀸이 올 수 있게 된다.

표기법

처음에는 2차원 논리배열을 통해 true, false로 표기하는 방식을 생각했지만 코드가 너무 복잡해지는 것을 확인했다.

그래서 단순히 1차원 배열에 값들을 적기로 했다.

1번째 줄부터 N번째 줄까지 퀸의 위치를 필수적으로 선택해야한다. 첫번째 줄에서의 재귀의 깊이를 0이라고 하면 N번째에 퀸을 놓았을 때 재귀의 깊이는 N-1이고 그 때 퀸의 위치를 기록한다면 기록되는 배열의 index 위치는 N-1일 것이다. 이 내용은 다음과 같은 표기를 가능하게 한다.

N번째줄에 퀸을 놓는 것 = 재귀의 깊이는 N-1 = 배열 index = N-1

4x4 체스판일 때 1행 2열, 2행 4열, 3행 1열, 4행 3열에 퀸을 둔다면 [2,4,1,3] 으로 기록되는 것이다.

	O
			O
O
		O

     [2,4,1,3]의 모습

메소드의 활용

메소드를 이용해 현재 위치에 퀸을 놓을 수 있는지 없는지 판단한다. 놓을 수 있으면 배열에 그 값을 기록하고 다음 줄(열)로 넘어간다.

놓을 수 없다면 그 다음 행을 탐색한다.

import java.util.Scanner;
public class Main {
	static int count=0; //개수를 세어줄 변수 count
	static int[] selected; //현재까지 놓은 퀸의 위치를 기록하는 곳
    
    //지금까지 체스판에 올려놓은 퀸의 위치와 겹치는지 아닌지 확인해준다
	static boolean check(int N, int Depth, int col) { //Depth가 곧 행, col은 열
		
        if(Depth==0)return true; //첫번째 줄에서는 제한 없이 퀸을 선택할 수 있다
        
		boolean judge=true;
        
		for(int i=0; i<Depth;i++) {
			if(Math.abs(i-Depth)==Math.abs(selected[i]-col) || selected[i]==col) {
             //대각선이거나 같은 줄이면 현재 위치에 퀸을 놓을 수 없다
				judge=false;
				i+=Depth;
			}
		}
		return judge;
	}
	
	
	static void nQueen(int N, int Depth) {
		if(Depth==N) { //재귀 깊이 N에 도달하면 모든 퀸을 놓았다는 뜻이므로 1개 추가한다
			count++;
			return;
		}
		for(int i=0; i<N;i++) {
			if(check(N,Depth,i)) { //메소드를 통해 퀸을 놓을 수 있으면 다음줄로 넘어간다(재귀호출)
				selected[Depth]=i; //값을 기록해주고
				nQueen(N,Depth+1); //다음 줄로 넘어간다
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		selected = new int[N];
		nQueen(N,0);
		System.out.print(count);
 }}