N-Queen알고리즘_Programmer

퀸을 첫번째 줄 첫번째 열부터 놓고 가능한 곳을 찾아간다.

퀸이 이런식으로 놓여졌다면 해당 열, 해당 줄은 놓을 수가 없고 또한 대각선 위치도 놓을 수 없다.

첫번째 줄부터 DFS를 통해 재귀적으로 놓을 수 있는 자리를 찾아간다.

문제점

1. 어떤 방법을 통해 재귀를 짤 것인가
2. 해당 위치에 퀸을 놓을 수 있는지 없는지 어떻게 판단할 것인가?

접근

처음에는 체스판의 배열이 2차원으로 되어있기 때문에 2차원 배열을 생성하여 접근하려 했지만,
해설을 보니 그럴 필요가 없다는 것을 깨달았다.

체스판의 행은 dfs의 level로 생각하고 열은 1차원배열을 생성하여 조회하면 되었다.

1. DFS 메소드를 하나 만들고
   LEVEL이 한단계씩 늘어날 때마다 놓을 수 있는 promissing메소드를 통해 boolean 검사하여 안된다면 리턴해서 되돌린다.

   LEVEL이 배열의 깊이와 같아진다면 결과값을 +1 하고 리턴한다.

   둘다 아니라면, for문을 체스판의 길이만큼 돌고 결과값 배열에 index값을 저장하고
   다음 DFS로 넘어간다.

2. promissing메소드는 for문을 통해 결과값 배열의 level위치 == 결과값 배열의 index위치가 같으면 리턴한다.(같은 줄에 있으면 안되기 때문에)

   같은 대각선에 있는지 체크하기 위해 level - i == arr[level] - arr[i] 값이 같은지 검사한다.

   

코드

package Problem;

import java.util.Arrays;
import java.util.Scanner;

public class N_Queen {
    /**
     * 문제 설명
     * 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
     *
     * 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
     *
     * Imgur
     * Imgur
     *
     * 체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.
     *
     * 제한사항
     * 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
     * n은 12이하의 자연수 입니다.
     * */
    static int x;
    static int arr[];
    static int result = 0;
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);

        x = 4;
        arr = new int[x+1];
        solution(x);
    }

    public static int solution(int n){
        int answer = 0;

        nQueen(0);
        //System.out.println(Arrays.toString(arr));
        System.out.println(result);
        return answer;
    }

    public static void nQueen(int level){
        if(!promissing(level)){
            return;
        }
        else if(level == arr.length-1){
            result++;
            System.out.println(Arrays.toString(arr));
            return;
        }
            for (int i = 1; i < arr.length; i++) {
                arr[level + 1] = i;
                nQueen(level + 1);
                }

        return;
    }

    public static boolean promissing(int level){
        for(int i=1; i<level; i++){
            if(arr[level] == arr[i]){
                return false;
            }

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