[Baekjoon] 백준 9663 N-Queen (G4^, 백트래킹) - Java

링크

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

9663번: N-Queen

 

 

 

문제 해석

N*N의 체스판에 N 개의 서로 공격을 할 수 없는 Queen을 놓을 수 있는 경우의 수를 구하시오. 

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	static int[][] map;
	static int N;
	static int count;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];

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

	}

	private static void solve(int idx) {
		// basis part
		// 행의 끝까지 가서 성공이라면
		if (idx == N) {
			count++;
			return;
		}

		// inductive part
		for (int i = 0; i < N; i++) {
			map[idx][i] = 1;
			if (check(idx, i)) {
				solve(idx + 1);
			}
			map[idx][i] = 0;
		}

	}

	// 1(Queue)인지 확인
	private static boolean check(int x, int y) {
		// 좌상
		for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
			if (map[i][j] == 1) {
				return false;
			}
		}

		// 상
		for (int i = x - 1; i >= 0; i--) {
			if (map[i][y] == 1) {
				return false;
			}
		}

		// 우상
		for (int i = x - 1, j = y + 1; i >= 0 && j < N; i--, j++) {
			if (map[i][j] == 1) {
				return false;
			}
		}

		return true;
	}
}

 

 

 

코드 해석

퀸의 이동방향 (출처 : 나무위키)

저처럼 체스를 할 줄 모르는 사람은 우선 Queen이 움직이는 방법에 대해서 알 필요성이 있습니다.

 

퀸은 상하좌우, 그리고 대각선으로 한 번에 무한히 나아갈 수 있는 말입니다. 

 

따라서 퀸의 직선상에는 퀸이 존재할 수 없다는 의미이기도 합니다.

 

 

 

해당 문제는 재귀적으로 문제를 해결할 수 있습니다.

 

다만 완전 탐색을 돌리는 경우 8 * 8 크기의 채스판에서 나올 수 있는 경우의 수는 $64C8$로 약 44억에 해당합니다.

즉 N이 최대 15인 해당 문제에서는 완전 탐색을 활용한다면 시간 초과가 나올 확률이 높습니다.

 

따라서 우리는 재귀적으로 돌리되, 가능성이 없다면 도중에 탐색을 멈추는 백트래킹 기법을 사용해야 합니다.

 

 

해당 문제의 해결 방법은 동일한 행에는 하나 이상의 퀸을 놓을 수 없다는 전제조건을 활용하여,

하나의 행에 퀸을 놓을 때마다 재귀를 반복하여 부르는 방법을 사용합니다.

 

퀸을 놓고나서 3방 탐색을 통해 탐색한 위치에 퀸이 존재하는지 여부를 확인하고, 퀸이 존재한다면 해당 자리는 사용할 수 없으므로 다른 자리로 이동합니다.

 

이때 3방 탐색은 좌상, 상, 우상으로만 이뤄지며, 이러한 이유는 N번째 행에 퀸을 놓을 때 기존에 놓여진 퀸은 N-1번째 까지이므로 N보다 값이 큰 행은 탐색할 필요가 없기 떄문입니다.

  

 

재귀를 돌리면서 만족하는 값이 나오면 conut를 증가시켜 주는 것으로 해를 찾을 수 있습니다.

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice