[백준/JAVA] 9663번: N-Queen

🔺 문제

9663번: N-Queen

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] arr; // 각 인덱스가 행을 의미하는 배열
    static int N;
    static int cnt = 0;
    
    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];
        
        nQueen(0);
        System.out.println(cnt);
    }
    
    // 1. 재귀호출
    private static void nQueen(int depth) { // depth : 행
        if(depth == N) {    // 행을 다 채우면, 카운트를 1 증가시키고 리턴
            cnt++;
            return;
        }
        
        for(int i = 0 ; i < N ; i++) {
            arr[depth] = i; // (depth, i)에 퀸 배치
            
            // 놓을 수 있는 위치일 경우, 재귀호출
            if(isPossible(depth)) {
                nQueen(depth + 1);
            }
            
        }
    }
    
    // 2. 놓을 위치가 다른 퀸으로부터 위협받는지 검사 (열과 대각선에 대해 생각해봐야함)
    private static boolean isPossible(int col) {    // 1차원 배열의 각 인덱스 위치 = '열'
        for(int i = 0 ; i < col ; i++) {
            if(arr[col] == arr[i]) {    // 같은 열에 존재할 경우
                return false;
            }
            else if(Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {    // 대각선 상에 놓인 경우
                return false;
            }
        }
        
        return true;
    }
}

✅ 해결 아이디어
✔ 백트래킹
- 퀸, 상하좌우 및 대각선으로 거리 제한 없이 한 방향으로 이동 가능하며,
  이 이동가능한 동선과 겹치지 않는 곳에 또 다른 퀸을 배치해야 함

- 각 행 별로 놓을 수 있는 위치에 있을 때 재귀호출하고, 만약 모두 배치되었다면 count하면서 경우의 수 찾아냄

 

🔍 체스판은 2차원 배열인데 왜 1차원 배열을 사용하는가?

-> arr의 크기가 행의 크기고, 각 인덱스에 있는 값이 열을 의미하게 함.

-> arr[depth] = i : (depth, i)에 퀸 배치

 

---

🔺 다른 풀이들

- 2차원 배열과 방향을 활용한 풀이

백준 9663번 : N-Queen (JAVA) 문제 풀이

[BOJ] 백준 9663번 N-Queen 백트래킹 (Java)

 

---

💬 느낀 점

체스 규칙을 몰라서.. 퀸이 어느 방향으로 움직일 수 있는지도 잘 몰랐다고 한다...ㅎ

코드 보고 배워서 나중에는 혼자 코드 작성할 수 있게 복습해야겠다!

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

[백준] 9663번 N-Queen java

[백준][JAVA알고리즘]9663번 풀이(N-Queen) - 초보도 이해하는 풀이