[백준] 9663번: N-Queen [JAVA-자바]

📝문제

www.acmicpc.net/problem/9663

9663번: N-Queen

💡Problem

• N-Queen 퍼즐은 N x N 크기의 체스판에 N 개의 퀸을, 서로 공격할 수 없도록 올려놓는 퍼즐입니다. (퀸은 체스에서 가장 강력한 기물로, 자신의 위치에서 상하좌우, 그리고 대각선 방향으로 이어진 직선 상의 어떤 기물도 공격할 수 있습니다)

• 백트래킹 알고리즘을 사용해야한다.
  • 전수조사를 하는것입니다.  다음 탐색을 진행하면서 그 탐색이 유망하지 않으면 무시하고 돌아가서 다시 탐색하는것을 말합니다.

🔑Solution

• 먼저, 배열을 1차원 배열로 받는다. 각 원소의 index를 '열', 원소 값을 '행'이라 생각한다.
  
  • 사실 이 부분은 생각하지 못해서 다른 사이트를 참고해서 풀었다.

• 재귀탐색을 하게되면 1차원 배열이기 때문에 '열'은 서로 다른 위치라 따로 검사할 필요가 없다.
• 다른 퀸과 같은 '행'에 위치하는지, 대각선상에 위치하는지를 검사한다.
• 만약 해당 위치에 놓을 수 있다면 다음 재귀를 호출하고, 아닐경우는 다음 반복문으로 넘어간다.

 

💻Code

import java.nio.file.Path;
import java.util.Scanner;

public class Main {

	static int[] queen;
	static int n;
	static int ans;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		queen = new int[n]; // 퀸을 배치할 행의 번호를 1~N번까지 사용 예정
		backtrack(0);
		System.out.println(ans);
	}

	static void backtrack(int row) {
		if (row == n) {
			ans++;
			return;
		}
		for (int j = 0; j < n; j++) {
			queen[row] = j;
			if (isOk(row)) { // 지금 row행의 퀸을 j번에 놓은게 괜찮다면??
				backtrack(row + 1);
			} // 지금 놨던 퀸이 자리가 안좋으면 ? 그냥 다음 j로 넘어가겠지.
		}
	}

	static boolean isOk(int col) {
		// 지금 row행에 놓은 퀸이 이전 퀸들에 영향을 안받는 자리에 있는지 확인
		for (int i = 0; i < col; i++) {
			// 현재 row 위치에 퀸이 있음
			if (queen[col] == queen[i])
				return false;
			/*
			 * 대각선상에 놓여있는 경우 
             		 * (열의 차와 행의 차가 같을 경우가 대각선에 놓여있는 경우다)
			 */
			if (Math.abs(col - i) == Math.abs(queen[i] - queen[col])) {
				return false;
			}
		}
		return true;
	}

}