백준 9663. N-Queen

백준/완전탐색

백준 9663. N-Queen

29살아저씨 2021. 8. 26. 19:46

🅰 백준 9663. N-Queen

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

✏️ 문제 풀이

✏️ 소스코드

package bruteforce;

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

public class Main_골드5_9663_손은성 {
	static int chess[], cnt, N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		chess = new int[N];

		queen(0);
		System.out.println(cnt);
	}

	private static void queen(int n) {
		if (!isAvailable(n-1)) {
			return;
		}
		if (n > N - 1) {
			cnt++;
			return;
		}
		for (int i = 0; i < N; i++) {
			chess[n] = i;
			queen(n + 1);
		}
	}

	private static boolean isAvailable(int n) {
		for (int i = 0; i < n; i++) {
			if (chess[i] == chess[n] || Math.abs(chess[i] - chess[n]) == n-i)
				return false;
		}
		return true;
	}

}

백준 9663. N-Queen

✅ 후기