[SW expert Academy] SWEA 2806번 N-Queen 자바(Java)

[D3] N-Queen - 2806

문제 링크

성능 요약

메모리: 20,684 KB, 시간: 170 ms, 코드길이: 1,103 Bytes

제출 일자

2023-10-24 16:19

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

 

문제 해결 방법
1. 놓을 수 있는 경우와 아닌 경우를 구분해야 함
2. 핵심은 대각선 확인하기.(행을 뺀 절대값과 열을 뺀 절대 값이 같으면 대각선 위치)

import java.util.Scanner;

class Solution
{
    static int[] arr;
    static int n,result;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
		for(int tc = 1; tc <= T; tc++)
		{
            n = sc.nextInt();
            arr = new int[n];
            result = 0;
            
            nQueen(0);
            
            System.out.println("#" + tc + " " + result);
		}
	}
    
    private static void nQueen(int depth){
        if(depth == n){
            result++;
            return;
        }
        
        for(int i = 0; i < n; i++){
            arr[depth] = i;
            
            if(isPossible(depth)){
                nQueen(depth+1);
            }
        }
    }
    
    private static boolean isPossible(int col){
        for(int i = 0; i < col; i++){
            if(arr[col] == arr[i]){
                return false;
            }
            
            if(Math.abs(i - col) == Math.abs(arr[i] - arr[col])){
                return false;
            }
        }
        return true;
    }
}