[BJ9663] N-Queen

 백준 - N-Queen 

문제 링크

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

9663번: N-Queen

 

문제 입출력

입출력1

8

92

입출력2

4

2

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
	static int ans, N;
	static int[] cols;


	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		cols = new int[N]; // 각 번호의 퀸이 어떤 열에 있는지를 저장

		setQueen(0);

		System.out.println(ans);

	} // end main


	private static void setQueen(int idx) {
		if (idx == N) {
			//System.out.println(Arrays.toString(cols));
			ans++;
			return;
		}

		for (int i = 0; i < N; i++) {
			cols[idx] = i;
			if (isAvailable(idx)) setQueen(idx + 1);
		}

	} // end setQueen


	private static boolean isAvailable(int idx) {
		// 이미 자리가 정해진 퀸들과 비교한다. 
		for (int i = 0; i < idx; i++) {
			if (cols[i] == cols[idx]) return false; // 같은 열에 있는 것 
			if (idx - i == Math.abs(cols[idx] - cols[i])) return false; // 대각선 
		}

		return true;
	} // end isAvailable
}

• 약간의 조합 문제라고 봐도 무방합니다.
• 하지만 퀸을 놓을 때 해당 열에 퀸을 놓을 수 있는지 아닌지 확인을 해야합니다.
• 그래서 isAvailable 함수를 이용해서 확인을 합니다.
• isAvailable 함수에서는 이미 자리가 정해진 퀸들과 같은 열에 있는지, 대각선에 있는지 확인을 하여 boolean 값을 리턴합니다.

 

 

 

 

 

 

 

 

 

# 백준 N-Queen java

---