[JAVA/백트래킹] 백준 9663 N-Queen

1. 문제

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

9663번: N-Queen

 

2. 코드

 

import java.util.Scanner;

// 백트래킹

public class Main {
    
    static int answer = 0;
    
    public static void nQueen(int[] arr, int n, int depth) {
        if(n == depth) {
            answer++;
            return;
        }

        
        for(int i = 0; i < n; i++) { // 한 row에서 퀸을 놓을 수 있는 경우 탐색
            arr[depth] = i; // 퀸 배치
            if(isPossible(arr, depth)) {
                nQueen(arr, n , depth + 1); // 다음 row 퀸 배치 탐색
            }
            
        }
    }
    
    public static boolean isPossible(int[] arr, int col) {
        for(int i = 0; i < col; i++) { // 미리 퀸을 놓은 row들을 확인
            if(arr[col] == arr[i])  // 퀸을 놓은 column이 겹치는 경우
                return false;
            else if(Math.abs(arr[col] - arr[i]) == Math.abs(col - i)) // 대각선에 위치한 경우
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        nQueen(arr, n, 0);
        
        System.out.println(answer);
    }

}