N-Queen 9663

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

이문제의 경우 처음에 했던 생각은 체스판위에 퀸들은 각각 다른 행에 위치하게 되니까 1차원 배열로 표현하고 배열의 인덱스가 행이고 값이 열이면 되겠다고 생각하였다. 이전에 알고리즘강의에서 봤던 문제라 이런 생각이 들었는지 모르겠다. 그래서 열에 해당하는 배열의 값을 dfs(깊이우선탐색) 방식으로 완전탐색 해서 무작위 숫자 배열을 만들어서 풀게되었다. 이때 체스판의 열에 해당하는 숫자들은 각자 고유하므로 자기자신의 숫자가 중복되지 않게 하였다.
그리고 재귀탐색할때 기존에 배열에 들어있는 퀸들의 행과 열이 지금 탐색중인 행과 열과 서로 공격이 가능한지 판단해서 백트랙킹(가지치기)를 하였다.

최악인 경우 N을 14로 받으면 최적화를 하지 않으면 14 factorial 의 경우의 수가 나온다
87178291200
약 87억

가지치기를 해서 나온 결과는 99280504
약 1억

import java.io.*;

public class Main
{
    static BufferedReader br;
    static int N;

    static boolean[] check;
    static int[] arr;

    static int ans = 0;

    //testcode
    //static int count = 0;

    public static void main(String[] args) throws IOException
    {
        inputProcess();
        search(0);

        System.out.println(ans);

        //testcode
        //System.out.println(count);
    }

    public static void inputProcess() throws IOException
    {
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        check = new boolean[N];
    }

    public static void search(int depth)
    {
        if(depth == N)
        {
            ans++;
            return;
        }

        int curDownCross;
        int curUpCross;
        for(int i = 0; i < N; ++i)
        {
            curDownCross = depth-i;
            curUpCross = depth+i;
            if(false == check[i] && false == col(depth, curDownCross, curUpCross))
            {
                check[i] = true;
                arr[depth] = i;
                search(depth+1);
                check[i]= false;
            }
        }
    }

    public static boolean col(int depth, int curDownCross, int curUpCross)
    {
        //count++;//testcode

        int preDownCross;
        int preUpCross;

        boolean IsCol = false;
        for(int i = 0; i < depth; ++i)
        {
            preDownCross = i - arr[i];
            preUpCross = i + arr[i];

            if(curDownCross == preDownCross || curUpCross == preUpCross) {
                IsCol = true;
                break;
            }

            if(true == IsCol)
                break;
        }

        return IsCol;
    }
}