공부 기록

먼저 플로이드를 이용하여 최단 거리를 구해두고 dfs 탐색하도록 한다.

import java.util.*;

public class Main {
	static int answer = Integer.MAX_VALUE;

	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();// 행성의 개수
		int start = in.nextInt();// 시작점
		int[][] mat = new int[n][n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				mat[i][j] = in.nextInt();
			}
		}

		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					mat[i][j] = Math.min(mat[i][j], mat[i][k] + mat[k][j]);
				}
			}
		}

		boolean[] visited = new boolean[n];
		visited[start] = true;
		dfs(visited, start, 0, 0, n, mat);

		System.out.println(answer);
	}

	public static void dfs(boolean[] isVisited, int temp, int sum, int depth, int n, int mat[][]) {
		if (depth == n - 1) {
			answer = Math.min(answer, sum);
			return;
		}

		for (int i = 0; i < n; i++) {
			if (!isVisited[i]) {
				isVisited[i] = true;
				dfs(isVisited, i, sum + mat[temp][i], depth + 1, n, mat);
				isVisited[i] = false;
			}
		}
	}

}