[Java] BOJ9663, 백준 - N-Queen

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

9663번: N-Queen

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
10 초	128 MB	43911	23073	15103	51.931%

문제

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

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

 

입력

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

 

출력

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

 

<풀이>

해당 행의 무슨 열에 퀸이 놓여있는지 저장할 배열: int[] arr

총 가능한 방법 수의 카운트: int cnt

 

재귀

완료조건: N행까지 퀸을 전부 놓았을 때 완료

 

종료조건: idx행에 퀸을 놓는다고 했을 때, idx-1번째 행까지 무슨 열에 퀸이 놓여있는지 확인한다.

             >조건1: 놓으려는 열에 퀸이 이미 놓아져있는 경우

             >조건2: 놓으려는 칸의 대각선 위치에 퀸이 이미 놓아져 있는 경우

조건1: 퀸이 이미 놓여있는 행을 보면서(1~idx-1 번째 행) 그 행에 놓아져 있는 열이(arr[j]) 현재 놓으려는 열과 같으면(arr[j] == i) 종료

조건2: 대각선의 위치에 있는지 판단하려면 행-행의 거리와 열-열의 거리가 같아야 함

 

반복조건: 해당 행마다 열을 한칸씩 옮겨가면서 계산해본다.(for문 이용)

 

소스코드

import java.io.*;

public class Main {
	private static int n;
	private static int cnt;
	private static int[] arr;

	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 + 1];
		cnt = 0;

		go(1);
		System.out.println(cnt);
	}

	private static void go(int idx) {
		// 완료조건: n행까지 퀸을 다 놨을 때
		if (idx > n) {
			cnt++;
			return;
		}

		// 지금 행은 idx행, 놓으려는 열은 i열
		// 놓은 행은 j행, 열은 arr[j]

		// 가능한 열을 판단
		changeCol: for (int i = 1; i <= n; i++) {
			// 행을 바꾸면서 이전까지 놓았던 것들을 본다.(현재 행은 idx행)
			for (int j = 1; j < idx; j++) {
				// 종료조건1: 같은 열에 있으면 안됨
				// 종료조건2: 대각선에 있으면 안됨
				if (arr[j] == i || Math.abs(idx - j) - Math.abs(i - arr[j]) == 0) {
					continue changeCol;
				}
			}
			arr[idx] = i;
			go(idx + 1);
			arr[idx] = 0;
		}

	}
}