백준 9663번 N-Queen java

 

9663번: N-Queen

 

문제

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

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

입력

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

 

N-Queen

 

백트래킹 문제를 설명할 때 가장 대표적으로 나오는 문제이다.

먼저 문제를 풀기 전에 고려해야 할 점은,  퀸은 왼쪽,오른쪽,위,아래,대각선 으로 이동이 가능하다는 것.

 

문제에서 요구하는 것이 N x N  크기의 체스판에 N개의 퀸을 배치했을때 퀸들이 서로를 죽이지 못하게 배치하는 경우의 수를 구하는 것이다.

 

1. N개의 정수형 배열을 선언하여 행과 열을 저장한다.

->가장 처음에는 1행1열에 퀸을 배치한다는 가정 하에 진행한다. 따라서 map[1] = 1 로 시작하게 된다.

 

2. 이제 1행에 퀸을 배치를 완료하였으니, 2행에 퀸을 배치해야한다. 반복문을 통해 2행에 1열~N열까지 배치가 가능한

위치를 탐색 후 , 배치가 가능하다면 다음 행으로 넘어가는 작업을 반복한다.

 

3. 이제 현재 탐색중인 행과 N(마지막 행) 이 동일하다면 1행~N행까지 N개의 퀸을 모두 배치했다는 뜻 이므로 count를 1 증가시킨다.

 

 

import java.util.Scanner;
public class Main {

	public static int n;
	public static int count;
	public static int[] map;

	public static boolean check(int[] map, int col) {
		for (int i = 1; i < col; i++) {
			if (map[i] == map[col]) 
				//같은 열이면 퀸을 배치할 수 없으므로 false
				return false;
			if (Math.abs(i - col) == Math.abs(map[i] - map[col])) 
				return false;
				//서로 대각선에 위치하고 있으면 퀸을 배치할 수 없으므로 false
		}
		return true;

	}

	public static void dfs(int[] map, int col) {
		// col(행) 이 n(마지막 행) 까지 도달한다면, 퀸의 배치가 끝난 상태로 count를 ++ 해준다.
		if (col == n) {
			count++;
		}

		else {
			for (int i = 1; i <= n; i++) {
				map[col + 1] = i; // 다음 행의 i열에 퀸을 배치 할 수 있는지 ?
				if (check(map, col + 1)) { // 이 위치에 퀸을 놓을 수 있다면
					dfs(map, col + 1); // 다시 dfs로 다음 퀸을 놓으러 간다.

				}

			}
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); // n x n 의 체스판과 n개의 퀸을 입력받는다.

		for (int i = 1; i <= n; i++) {
			map = new int[n + 1]; // 1행부터 고려하기 때문에 , map[0]은 사용하지 않음.

			map[1] = i; // 1행 i열에 퀸을 놓는다.

			dfs(map, 1);

		}
		System.out.println(count);

	}
}