[백준 / Java] 9663번 N-Queen

사용한 알고리즘(백트래킹)

https://cobi-98.tistory.com/22

[필수 알고리즘] 재귀호출 기본 -백트래킹(Backtracking)

 

🔒 9663번 N-Queen

✔ 문제 설명

🚩 요구사항 분석

Queen 이 움직일 수 있는 범위

• 탐색 과정에서 값을 담을 count 변수 생성
• 정사각형의 체스판 이므로 1차원 배열을 사용해 index를 열 , value 값을 행을 가지는 int 배열 생성
• 같은 열과 같은 행(세로 가로)에 존재하는 경우
• 대각선에 존재하는 경우 
• 재귀 반복. 
• 행을 다 채우면 count++; 

 

🔑 문제풀이

해당 문제의 요구사항을 파악을 하는 건 쉽지만 대각선 코드를 구현하는 게 쉽지 않았다.

 

문제 풀이는 열을 계속 추가해 나아가면서 행에 놓을 수 있는지 판단하여 값을 채우고 행을 다 채우면 count를 추가하는 방식이다.

 

그렇다면 판단을 확인하기 위해 Possibility함수를 확인해 보자.

재귀를 ++ 해 나가면서 열을 추가해 나아감으로 열은 서로 다른 위치이고

value 인 값을 같은 행을 확인하기 위해 해당 arr [col] (행)과 arr [i] (i열의 행이) 같으면 false

대각선 조건을 확인하기 위해 열의 차와 행의 차가 같은 경우 false 처리를 했다.

ex) (2,0,0,0) -> arr [0] = 2 , arr [1] = 0 arr [2] = 0 arr [3]=0

노란색 x 중 하나를 예시로 arr [1] = 1 은 대각선인 경우다.

행-행 |(2-1)| == 열-열 |(0-1)| 이므로 대각선인 경우이므로 false 처리가 된다.

 

그렇게 되면  행 별로 놓을 수 있는 위치에 재귀호출로 다음 열을 찾아가고 배치가 모두 되었다면 count를 해주면서 경우의 수를 찾아내었다.

import java.util.Scanner;

public class Main {
    public static int[] arr;
    public static int N;
    public static int count = 0;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N];

        nQueen(0);
        System.out.println(count);
    }

    public static void nQueen(int depth){
        // 행을 다 채우면 카운트를 1 증가시키고 리턴시킨다.
        if(depth == N){
            count++;
            return;
        }

        for (int i = 0; i < N; i++) {
            arr[depth] = i;
            // Possibility() 해당 열에서 i 번째 행에 놓을 수 있는지를 검사하는 함수
            if(Possibility(depth)){
                nQueen(depth + 1);
            }
        }

    }

    public static boolean Possibility(int col) {

        for (int i = 0; i < col; i++) {
            // 해당 열의 행과 i열의 행이 일치할경우 (같은 행에 존재할 경우)
            if (arr[col] == arr[i]) {
                return false;
            }

            /*
             * 대각선상에 놓여있는 경우
             * (열의 차와 행의 차가 같을 경우가 대각선에 놓여있는 경우다)
             */
            else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
                return false;
            }
        }

        return true;
    }
}