[Java] 백준 #9663 (백트랙킹)

📍 출처

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

📝 문제

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

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

⌨️ 입력

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

🖨 출력

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

⌨️ 예제 입력

8

🖨 예제 출력

92

📚 내가 제출한 코드

import java.io.IOException;
import java.util.Scanner;

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

        public static void main(String[] args) throws IOException{
        
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        arr = new int[N];
        qeen(0);
        System.out.println(count);

    } 
    public static void qeen(int col){
        if(col == N){
            count++;
            return;
        }

        for(int i = 0 ; i < N ; i++){
            arr[col] = i;
            
            if(posibility(col)){
                qeen(col + 1);
            }
        }
    }

    public static boolean posibility(int col){
        for(int i = 0 ; i < col ; i++){
            if(arr[col] == arr[i]){
                return false;
            }

            if(Math.abs(col - i) == Math.abs(arr[col] - arr[i])){
                return false;
            }
        }
        return true;
    }
}

✏️ 내가 제출한 코드에 대한 설명

• 2차원 배열을 1차원배열로 구현
  • 1차원 배열의 index : 2차원배열의 열
  • 1차원 배열의 값 : 2차원배열의 행
• 퀸이 놓이지 못하는 조건
  • 다른 퀸의 행과 열이 같을 때(배열의 index는 무조건 다르기때문에 열은 비교 할 필요 없음)
  • 다른 퀸과 대각선으로 놓여 있을때(두 퀸의 행의 차, 열의 차 같으면 대각)