📌 문제

[9663] N-Queen

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

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

⬇️ 입력

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

⬆️ 출력

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

💡 코드

✅ 체알못인 나는 '퀸 N개를 서로 공격할 수 없게 놓는 문제'가 뭔지 몰랐고.. 급하게 구글링을 통해 알아본 결과 하나의 퀸을 한 행에 놓았을 때 해당 위치로부터 가로, 세로, 대각선 위치에는 다음 퀸을 놓을 수 없게 배치하는 문제였다!

nQueen() 메서드는 행 depth를 입력받는다. 가장 먼저 0행을 입력받아 for문을 통해 0번부터 n-1번 열까지 퀸을 놓을 수 있다. 이 때 배열 chess[]에서 인덱스(depth)는 행을 의미하고, 인덱스에 해당하는 요소의 값을 열으로 생각하여 풀었다. depth행 i번째 열에 퀸을 놓고 isPossible(depth)를 호출하여 해당 위치에 퀸을 놓을 수 있는지 판별한다.

isPossible(col) 메서드는 두가지 조건식을 통해 판별을 수행한다. 첫번째 조건문을 통해 판별해야 하는 위치와 같은 열에 퀸이 존재하는지 확인하고, 이미 존재한다면 false를 반환한다. 해당 조건문을 통과하면 다음 조건문을 통해 판별해야 하는 위치가 대각선인지 확인한다. 이 때, 해당 행 - 판별 행의 값과 해당 열 - 판별 열의 값이 같다면 대각선에 위치한다는 뜻이므로 역시 false를 리턴한다. 모든 행에 대해 판별을 마친 후에도 겹치지 않는다면 true를 리턴한다. isPossible(depth)의 값이 true이면 해당 위치에 퀸을 놓고 nQueen(depth+1)을 호출하여 다음 행에 퀸을 놓을 위치를 찾고, false라면 다음 열로 이동하여 해당 과정을 반복한다.

import java.io.*;
import java.util.*;
public class Main {
	
	static int n;
	static int[] chess; // 행
	static int cnt = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		n = Integer.parseInt(br.readLine());
		chess = new int[n];
		
		nQueen(0);
		bw.write(cnt + "");
		
		br.close();
		bw.close();
	}
	
	static boolean isPossible(int col) {
		
		for(int i=0;i<col;i++) { 
			
			// 같은 열에 존재할 경우
			if(chess[col] == chess[i]) return false;
			
			// 대각선 상 놓여있는 경우
			else if(Math.abs(col-i) == Math.abs(chess[col] - chess[i]))
				return false;
		}
		
		return true;
	}
	
	static void nQueen(int depth) { // 행
		
		if(depth == n) {
			cnt++; 
			return;
		}
		
		for(int i=0;i<n;i++) { // 열
			chess[depth] = i;
			
			if(isPossible(depth)) {
				nQueen(depth+1);
			}
		}
	}
}