[BOJ] 9663 - N-Queen (Java)

알고리즘

• 브루트포스 알고리즘
• 백트래킹

1. 문제

• N x N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제
• 각 퀸은 같은 행, 열, 또는 대각선 상에 있으면 서로 공격할 수 있다.

2. Idea

• 백트래킹을 사용하여 모든 가능한 퀸의 배치를 생성하고, 유효한 경우에만 진행하여 가능한 배치의 수를 세는 방식으로 진행

3. 풀이

3.1. 변수 선언 및 초기화

• arr: 각 행에 퀸이 위치한 열의 정보를 저장하는 배열
• N: 행/열 수
• count: 가능한 퀸의 배치의 수를 저장하는 변수

public static int[] arr;
public static int N;

3.2. Possibility 메소드 구현

• Possibility: 현재 위치에 퀸을 놓을 수 있는지를 검사하는 메소드
• 같은 열에 퀸이 없고, 대각선상에 퀸이 없는지 확인
• 가능한 퀸의 배치를 발견할 때마다 count++

	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;
	}

3.3. nQueen 메소드 구현

• nQueen: 재귀적으로 모든 퀸을 놓는 경우의 수를 탐색하는 메소드
• 현재 행에 퀸을 놓을 수 있는 모든 열에 대해 시도하고, 가능한 경우에는 다음 행으로 진행
• 재귀 호출을 통해 모든 가능한 퀸의 배치를 시도 (브루트포스)

	public static void nQueen(int depth) {
		// 모든 원소를 다 채운 상태면 count 증가
		if (depth == N) { count++; return; }
 
		for (int i = 0; i < N; i++) {
			arr[depth] = i;
			// 놓을 수 있는 위치일 경우 재귀호출
			if (Possibility(depth)) { nQueen(depth + 1); }
		}
 
	}

3.4. nQueen 메소드 호출

• 0번째 행부터 탐색해야 하므로 nQueen(0) 수행

nQueen(0);

3.5. 결과 출력

System.out.println(count);

4. 전체코드

import java.io.*;
 
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 증가
		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;
	}
}