[백준] 9663 N-Queen (JAVA)

풀이

 위의 문제는 백트랙킹의 기초적인 문제라고 할수있겠다. 이 문제를 접하게 된 경로는 solved에서 문제를 풀다 백트랙킹 문제를 맞닥뜨려 풀려고 하였으나 관련문제를 풀어본적이 없어 풀지를 못했다. 이러한 내 자신에거 실망을 하여 백트랙킹의 기초문제를 풀려고 찾아보았고 가장 기초적인 문제를 찾아서 풀었다.

 문제는 크기가 n x n인 체스판에서 퀸을 몇개나 놓을수 있냐는 문제이다. 이러한 방식은 마지 스택을 이용한 미로찾기 처럼 하면되는데 미로찾기에서는 이차원의 배열을 만들어 사용했다면 여기서는 1차원의 배열을 이용해 열을 index값으로,  행을 원소값으로 생각하여 풀면 된다. 자세한것은 아래의 코드를 보면 될듯하다.

 

코드 

import java.util.Scanner;

class Main{

    public static int []arr;
    public static int N;
    public static int count = 0;

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

    public static void nQueen(int depth){
        if(N == depth) {
            count++;
            return;
        }
        for(int i=0; i<N; i++){
            arr[depth] = i;
            if(Possibility(depth))
                nQueen(depth+1);
        }
    }

    public static boolean Possibility(int col){
        for(int i=0; i<col; i++){
            if(arr[col] == arr[i])
                return false;
            else if(Math.abs(col-i) == Math.abs(arr[col] - arr[i]))
                return false;
        }
        return true;
    }
}