230710 GPS

private static final int INF = 1000000;

public int solution(int n, int m, int[][] edgeList, int k, int[] gpsLog) {
	int[][] road = new int[n + 1][n + 1];

	for (int[] edge : edgeList) {
		int s = edge[0], e = edge[1];
		road[s][e] = 1;
		road[e][s] = 1;
	}

	int[][] dp = new int[k][n + 1];
	for (int[] row : dp) {
		Arrays.fill(row, INF);
	}

	dp[0][gpsLog[0]] = 0;

	for (int i = 1; i < k; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = Math.min(dp[i][j], dp[i - 1][j]);
			for (int node = 1; node <= n; node++) {
				if (road[j][node] == 1) {
					dp[i][j] = Math.min(dp[i][j], dp[i - 1][node]);
				}
			}
			if (j != gpsLog[i]) {
				dp[i][j]++;
			}
		}
	}

	return dp[k - 1][gpsLog[k - 1]] < INF ? dp[k - 1][gpsLog[k - 1]] : -1;
}

출처:https://school.programmers.co.kr/learn/courses/30/lessons/1837