[프로그래머스] GPS (JAVA)

문제

카카오 택시 개발자 Jay-G는 다음 업데이트를 준비하기 위해 개선사항을 위한 여러 피드백을 받았다. 그중에서 손님이 자주 탑승하는 위치를 추천해주었으면 한다는 의견이 많았다.

다음 업데이트 준비를 위해 Jay-G는 택시의 승하차 및 이동 경로를 수집하여 분석하기 시작하였다. 데이터를 분석하던 Jay-G는 몇 가지 특이사항을 발견했다. 택시의 이동 경로를 GPS를 통해 수집하게 되는데, GPS 신호 불량, 통신 오류 등 다양한 원인으로 위치의 오류가 발생한 것을 알게 되었다. 다만 승차 위치와 하차 위치는 오류가 없는 것으로 확인이 되었다.

개발자 Jay-G는 수집한 이동 경로의 오류를 최소한으로 수정하여 좀 더 정확한 이동 경로를 구하고 싶어 한다.

택시는 다음과 같은 조건으로만 이동한다. 먼저 택시는 거점을 이동해 다니며, 거점 간의 이동은 해당하는 도로가 있는 경우에만 가능하다. 또한, 교통 상황에 따라 택시는 한 거점에 머무를 수 있고, 왔던 길을 되돌아갈 수 있다. 모든 도로는 방향이 별도로 없는 왕복 도로이다.

Code

import java.util.*;
class Solution {
    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
        List<List<Integer>> list = new ArrayList<>();
		int[][] dp = new int[k][n+1];
		for(int i=0 ; i<=n ; i++) {
			list.add(new ArrayList<>());
		}
		for(int[] ed : edge_list) {
			list.get(ed[0]).add(ed[1]);
			list.get(ed[1]).add(ed[0]);
		}
		
		for(int[] arr : dp) {
			Arrays.fill(arr, k+1);
		}
		dp[0][gps_log[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 num : list.get(j)) {
					dp[i][j] = Math.min(dp[i][j], dp[i-1][num]);
				}
                dp[i][j] += gps_log[i] == j ? 0 : 1;
			}
		}
		return dp[k-1][gps_log[k-1]]>k?-1:dp[k-1][gps_log[k-1]];
    }
}

Comment

문제 제출 시, 한번의 run으로 여러 케이스를 돌리다보니
내 코드의 정확도를 알수 없없음.
결국 남의 코드를 참고했지만, 그래도 완전 이해함. 다시 한번 풀기 필요.