GPS

문제

프로그래머스 - GPS

---

문제 해결 아이디어

목표는 수정 횟수(오차로 기록된 위치를 바꾼 횟수)를 최소화하여 실제 이동 가능한 경로로 만들기, 시간 t에 v 정점에 있을 때 수정 횟수를 DP로..!

조건

• 택시는 인접한 두 거점 사이를 이동
• 이동 하지 않고 머무르기 가능
• 주어진 GPS 로그의 시작(첫번째)와 도착(마지막) 거점은 바꿀 수 없고, 나머지 위치는 원하는 거점으로 수정가능

DP 접근

각 시간 t (0 ≤ t < k)에서, 택시가 거점 v에 있을 때 지금까지 수정한 최소 횟수를 dp[t][v]라고 한다.

초기 상태:
t=0에서는 GPS 로그의 첫 번째 위치 s가 고정되므로 dp[0][s] = 0이고, 다른 거점은 Integer.MAX_VALUE로 둔다.

전이:
t에서 v에 있을 때, t+1에는 v에서 이동 가능한 모든 거점 w (자신 포함)로 이동할 수 있다. 이때, GPS 로그에 기록된 t+1번째 값과 w가 같으면 추가 오류 수정 없이, 다르면 1회의 오류 수정 카운트

dp[t+1][w] = min(dp[t+1][w], dp[t][v] + (w == gps_log[t+1] ? 0 : 1))

k-1 시점에 GPS 로그의 도착 위치에 도달하는 최소 수정 횟수가 정답!
도달 불가능하면 -1을 반환

---

코드

import java.util.*;

class Solution {
    static List<Integer>[] graph;
    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
        // 1부터 n까지 정점, 양방향 간선으로 인접 리스트 생성
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
            // "머무르기" 가능
            graph[i].add(i);
        }
        for (int[] edge : edge_list) {
            int a = edge[0];
            int b = edge[1];
            graph[a].add(b);
            graph[b].add(a);
        }
        
        // dp[t][v] : 시간 t에 v에 있을 때까지 수정한 최소 횟수
        int[][] dp = new int[k][n + 1];
        for (int i = 0; i < k; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        // 시작 위치는 gps_log[0]
        dp[0][gps_log[0]] = 0;
        
        // 마지막 위치 gps_log[k-1]는 수정 불가
        for (int t = 0; t < k - 1; t++) {
            for (int v = 1; v <= n; v++) {
                if (dp[t][v] == Integer.MAX_VALUE) continue;
                // v에서 이동 가능한 모든 거점 w (v 자신 포함)
                for (int w : graph[v]) {
                    int cost = (w == gps_log[t + 1] ? 0 : 1);
                    dp[t + 1][w] = Math.min(dp[t + 1][w], dp[t][v] + cost);
                }
            }
        }

        int answer = dp[k - 1][gps_log[k - 1]];
        return (answer == Integer.MAX_VALUE ? -1 : answer);
    }
}