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

www.acmicpc.net/problem/9663

9663번: N-Queen

 

---

• 문제

 

 

 

 

백트래킹의 대표적인 문제인 N Queen 문제다. 몇 가지 규칙만 알면 쉽게 풀 수 있으니 차근차근 알아보도록 하자.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

문제에서 일단 체스판 크기가 주어지면 해당 체스판 안에서 퀸이 서로 공격할 수 없도록 배치하는 경우의 수를 찾으면 된다.

퀸이 이동할 수 있는 위치는 대부분 알겠지만 상하좌우 및 대각선으로 거리 제한 없이 한 방향으로 이동이 가능하다. 즉, 다음 그림과 같이 움직일 수 있다.

 

이 이동가능한 동선과 겹치지 않는 곳에 또 다른 퀸을 배치해야 하는 것이 관건이다.

 

그럼 조건부터 하나하나씩 따져보자.

 

 

 

 

 

4x4 크기의 체스판이 있다고 가정해보자.

 

1) 첫번 째 열에서 아래와 같이 놓여져있다고 가정한다.

위 위치대로 퀸이 놓여져 있으면 다음 X표시에는 또 다른 퀸을 놓을 수 없다. 즉, 빈 공간에 넣어야 한다. 

 

 

 

2) 다음 열에서 빈 공간은 첫번 째 행만 된다. 즉 아래 그림처럼 다음 열에 퀸을 추가할 수 있겠다.

 

그리고 마찬가지로 두 번째 행의 퀸이 이동가능한(공격 가능한) 경로를 모두 X표시 해준다.

 

 

 

 

3) 다음 행에서 빈 공간은 첫 번째 열만 된다. 즉 아래처럼 그 다음 행에 퀸을 추가 할 수 있다.

그럼 최종적으로 남는 공간이 하나 남는다.

즉, 4 X 4 에서 경우의 수 중 하나가 다음과 같다.

 

 

 

 

 

 

이런식으로 각 행 별로 놓을 수 있는 위치에 있을 때 재귀호출을 해주고, 만약 모두 배치 되었다면 count 를 해주면서 경우의 수를 찾아내면 된다.

 

 

그럼 두 가지가 문제일 것이다.

 

   1. 재귀호출을 어떻게 할 것인가

   2. 퀸을 놓을 수 있는지 여부를 어떻게 조건문으로 판별 할 것인가

 

 

 

 

먼저, 배열을 받을 때 2차원 배열로 해도 되지만, 1차원 배열로 받아도 된다. 무슨말이냐면 각 원소의 index를 '열'이라 생각하고, 원소 값을 '행'이라 생각하는 것이다.

위 그림을 1차원 행렬로 표현하자면 다음과 같이 표현할 수 있다.

[2, 0, 3, 1]  (배열은 0 부터 시작하므로 첫 번째 위치는 0 이다.)

 

즉, 첫 번째 열부터 한 개씩 채워나가면서 놓을 수 있는 위치라면 재귀호출을 하면서 채워나가는 것이다.

 

 

1. 재귀 호출 부분

 

그럼 1차원 배열을 토대로 재귀호출 함수를 간략하게 짠다면 다음과 같을 것이다.

public static int[] arr;
public static int N;	// 체스판의 크기
public static int count = 0;


public static void nQueen(int depth) {
	// 행을 다 체우면 카운트를 1 증가시키고 리턴시킨다.
	if (depth == N) {
		count++;
		return;
	}

	for (int i = 0; i < N; i++) {
		arr[depth] = i;
		// Possibility() 해당 열에서 i 번째 행에 놓을 수 있는지를 검사하는 함수
		if (Possibility(depth)) {
			nQueen(depth + 1);
		}
	}
}

 

 

 

2. 놓을 위치가 다른 퀸으로부터 위협받는지를 검사하는 조건문

public static boolean Possibility(int col) {

	for (int i = 0; i < col; i++) {
		// 해당 열의 행과 i열의 행이 일치할경우 (같은 행에 존재할 경우) 
		if (arr[col] == arr[i]) {
			return false;
		} 
		
		/*
		 * 대각선상에 놓여있는 경우
		 * (열의 차와 행의 차가 같을 경우가 대각선에 놓여있는 경우다)
		 */
		else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
			return false;
		}
	}
	
	return true;
}

 

 

주석으로 설명해놓긴 했다만 혹여 이해가 안가면 댓글 남겨주시면 최대한 빠르게 답변드리도록 하겠다.

 

일단, 간략하게 설명하자면, 1차원 배열에 각 인덱스(위치)는 '열'을 가리키고, 해당 인덱스의 값은 '행'을 의미한다. 이 탐색과정에서 위 재귀호출 코드를 보면 알겠지만, 첫 번째 열에 '행'의 값을 찾고, 두 번째 열에 또다른 행의 값을 찾고.. 이렇게 나아가는 과정이다. 즉, 재귀탐색을 하게되면 기본적으로 '열'은 서로 다른 위치이니 우리가 검사할 것은 다른 퀸과 동일한 '행'에 위치하는지와 대각선상에 위치하는지를 검사하면 된다. 만약 해당 위치가 공격받지 않는 위치라면 다음 재귀를 호출하고, 아닐경우는 다음 반복문으로 넘어간다.

 

 

 

그렇다면 이제 완성된 코드와 함께 같이 보도록 하자.

 

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이번에는 출력이 단일, 즉 경우의 수를 출력하는 문제라 입력의 차이만 비교하여 성능이 어떻게 차이나는지를 볼 것이다. 즉, 두가지 입력 방법을 쓸 것이다.

 

1 . Scanner 

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;

public class Main {

	public static int[] arr;
	public static int N;
	public static int count = 0;

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		arr = new int[N];

		nQueen(0);
		System.out.println(count);

	}

	public static void nQueen(int depth) {
		// 모든 원소를 다 채운 상태면 count 증가 및 return 
		if (depth == N) {
			count++;
			return;
		}

		for (int i = 0; i < N; i++) {
			arr[depth] = i;
			// 놓을 수 있는 위치일 경우 재귀호출
			if (Possibility(depth)) {
				nQueen(depth + 1);
			}
		}

	}

	public static boolean Possibility(int col) {

		for (int i = 0; i < col; i++) {
			// 해당 열의 행과 i열의 행이 일치할경우 (같은 행에 존재할 경우) 
			if (arr[col] == arr[i]) {
				return false;
			} 
			
			/*
			 * 대각선상에 놓여있는 경우
			 * (열의 차와 행의 차가 같을 경우가 대각선에 놓여있는 경우다)
			 */
			else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
				return false;
			}
		}
		
		return true;
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

아마 2차원 배열을 쓴다면 꽤 고생할 수도 있다.. 물론 필자처럼 1차원 배열 구조를 index를 '열', 각 index의 값을 '행'이 아닌 반대로 생각하고 풀어도 된다. 그건 여러분들이 편한 방식대로 하면 되기 때문에 자유롭게 구상해보면 좋을 것 같다.

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.

 

 

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

public class Main {

	public static int[] arr;
	public static int N;
	public 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());
		arr = new int[N];

		nQueen(0);
		System.out.println(count);

	}

	public static void nQueen(int depth) {
		// 모든 원소를 다 채운 상태면 count 증가 및 return 
		if (depth == N) {
			count++;
			return;
		}

		for (int i = 0; i < N; i++) {
			arr[depth] = i;
			// 놓을 수 있는 위치일 경우 재귀호출
			if (Possibility(depth)) {
				nQueen(depth + 1);
			}
		}

	}

	public static boolean Possibility(int col) {

		for (int i = 0; i < col; i++) {
			// 해당 열의 행과 i열의 행이 일치할경우 (같은 행에 존재할 경우) 
			if (arr[col] == arr[i]) {
				return false;
			} 
			
			/*
			 * 대각선상에 놓여있는 경우
			 * (열의 차와 행의 차가 같을 경우가 대각선에 놓여있는 경우다)
			 */
			else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
				return false;
			}
		}
		
		return true;
	}
}

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 20808342  -  방법 2 : BufferedReader 

채점 번호 : 20808336  -  방법 1 : Scanner 

 

 

탐색 과정이 워낙 많다보니 아무래도 입력에서의 차이는 메모리 차이가 가장 두드러지는 것 같다.

사실 그럴법도 한 것이, N=14 일경우 총 경우의 수가 365596개나 된다고 하니.. 결코 적은 경우의 수는 아니다.

---

• 정리

 

이번 문제는 백트래킹을 '활용했다'라고 할 법한 문제다운 문제였다. 그렇다보니 처음 접하는 분들은 매우 어렵게 다가왔을 수도 있을 것 같다. 특히 대각선에 놓여있는 경우를 어떻게 조건화 해야하는지 아이디어가 잘 떠오르지 않으신 분들이 꽤나 있는 것 같다. 혹여 필자가 설명이 미흡하다거나, 이해가 안되는 부분이 있다면 댓글로 남겨주길 바란다.