[SW 아카데미] 1940. N-Queen #

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=JAVA&select-1=3&pageSize=30&pageIndex=1 

SW Expert Academy

 

1. 1차원 배열을 이용

: 인덱스를 열로, 원소 값을 행으로

-> 대각선 체크와 행체크만 하면 된다.

 

: 열을 채우기 위해 -> 재귀 호출

: 재귀 호출 종료 조건 : 모든 원소 채웠을 때 -> count++후 리턴

-> 해당 열까지 돌면서 퀸을 둘 수 있는지 체크하는 함수 호출 -> 대각선 체크, 행 체크 수행

 

-> 행체크 : 열 배열의 원소값이 같을 때 arr[i]==arr[col]

-> 대각선 체크 : 행 거리와 열 거리가 같을 때 Math.abs(arr[col]-arr[i]) == Math.abs(arr[col]-arr[i])

 

2. 2차원 배열 이용

: 대각선 체크, 행체크, 열체크

package sw2806;


import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{

    static int N;
    //인덱스를 열로, 원소 값을 행으로
    //-> 같은 열에 존재하는 경우가 제거된다.
    static int[] arr;
    static int count;




    //1.재귀 호출
    public static void isFunc(int depth){
        //1. 모든 원소를 다 채운 상태면 count 증가 및 return
        //2. 놓을 수 있는 위치일 경우 재귀호출
        if(depth==N){
            count++;
            return;
        }
        for(int i=0;i<N;i++){
            arr[depth]=i;

            if(isValid(depth)){
                isFunc(depth+1);
            }
        }
    }
    //2.퀸 놓을 수 있는지 조건문 체크
    public static boolean isValid(int col){
        //1. 해당 열의 행과 i열의 행이 일치할경우 (같은 행에 존재할 경우)
        //2. 대각선상에 놓여있는 경우 -> (열의 차와 행의 차가 같을 때)


        //당연히 해당 열까지만 체크
        for(int i=0;i<col;i++) {
            if (arr[i]==arr[col]){
                return false;
                //열의 차 : Math.abs(col-i)
                //행의 차 : arr[col]-arr[i]
            }else if(Math.abs(col-i)==Math.abs(arr[col]-arr[i])){
                return false;
            }
        }
        return true;
    }
    
    public static void main(String args[]) throws Exception
    {
        System.setIn(new FileInputStream("src/sw2806/sample_input.txt"));


        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();


        for(int test_case = 1; test_case <= T; test_case++)
        {
            count=0;
            //N*N 보드에 N개의 퀸을 서로 공격 못하는 방법으로 퀸을 놓는 수
            //같은 행 같은 열 같은 대각선 -> 이면 안된다.
            N=sc.nextInt();
            arr=new int[N];

            isFunc(0);
            System.out.println("#"+test_case+" "+count);
        }
    }
}