백준 17182 java

플로이드 워셜 결과에 대해 DFS를 수행한다. DFS도 다시 연습하겠다.

import java.util.Scanner;

public class bj17182 {
    static Scanner scanner = new Scanner(System.in);
    static int[][] planet;
    static boolean[] visited;
    static int K;
    static int minimum = Integer.MAX_VALUE;

    public static void main(String[] args) {
        inputData();
        System.out.println(findAnswer());

        scanner.close();
    }

    //행렬은 0부터 시작한다,
    public static void inputData() {
        System.out.println("\ninputData()");
        int N, i, j, T;

        N = scanner.nextInt();
        K = scanner.nextInt();
        planet = new int[N][N];
        visited = new boolean[N];
        for (i = 0; i < planet.length; i++) {
            for (j = 0; j < planet.length; j++) {
                T = scanner.nextInt();
                planet[i][j] = T;
            }
        }
    }

    public static int findAnswer() {
        System.out.println("\nfindAnswer");
        //int answer = 0;

        floydWarshall();
        visited[K] = true;
        DFS(1, K, 0);
        //answer = minimum;

        return minimum;
    }

    public static void floydWarshall() {
        System.out.println("\nfloydWarshall()");
        int i, j, k;
        int N = planet.length;

        for (k = 0; k < N; k++) {
            for (i = 0; i < N; i++) {
                for (j = 0; j < N; j++) {
                    planet[i][j] = Math.min(planet[i][j], planet[i][k] + planet[k][j]);
                }
            }
        }

        System.out.println("플로이드 워셜 결과");
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                System.out.print(planet[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void DFS(int depth, int start, int distance) {
        int N = planet.length;
        int i;

        if (depth == N) {
            minimum = Math.min(minimum, distance);
            System.out.println("minimum : " + minimum);
            return;
        }
        for (i = 0; i < N; i++) {
            if (i == start) {
                continue;
            }
            if (!visited[i]) {
                visited[i] = true;
                DFS(depth + 1, i, distance + planet[start][i]);// 깊이, 출발점, 거리
                visited[i] = false;
            }
        }
    }
}