외판원 순회 2 10971

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

완전탐색으로 풀었다. 자기자신을 제외한 숫자 조합을 만들어서 풀었다
0123
0132
0213
0231
0312
0321

1023
1032
1203
1230
1302
1320

등등의 조합을 만들었다

시간복잡도는 N팩토리얼 인듯
따라서 O(10!) = 3628800

경로에 0 이 있는 경우 제외 시켜야 하는 예외처리를 빼먹어서 시간이 더 걸렸다;;

import java.io.*;
import java.util.*;

public class Main
{

    static int N;
    static int[][] cities;

    static int[] arr;
    static boolean[] checked;

    static int ans = Integer.MAX_VALUE;

    static BufferedReader br;

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

        search(0);

        System.out.println(ans);
    }

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

        N = Integer.parseInt(br.readLine());
        cities = new int[N][N];

        arr = new int[N];
        checked = new boolean[N];

        String[] input;
        for(int i = 0; i < N; ++i)
        {
            input = br.readLine().split(" ");
            for(int j = 0; j < N; ++j)
            {
                cities[i][j] = Integer.parseInt(input[j]);
            }
        }
    }

    //같은 숫자 X
    //동일 원소 조합 O
    public static void search(int depth)
    {
        if(depth == N)
        {
            int sum = 0;
            for(int i = 0; i < arr.length; ++i)
            {
                if(i+1 < N)
                {
                    if(cities[arr[i]][arr[i+1]] == 0)//갈 수 없는 경로 있는 경우는 버린다
                    {
                        return;
                    }

                    sum += cities[arr[i]][arr[i+1]];
                }
                else
                {
                    if(cities[arr[i]][arr[0]] == 0)//갈 수 없는 경로 있는 경우는 버린다
                    {
                        return;
                    }

                    sum += cities[arr[i]][arr[0]];
                }

            }

            ans = Math.min(ans, sum);
            return;
        }

        for(int i = 0; i < N; ++i)
        {
            if(false == checked[i])
            {
                checked[i] = true;

                arr[depth] = i;
                search(depth+1);
                checked[i] = false;
            }
        }
    }
}