[프로그래머스] GPS

문제 설명

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

문제 풀이

• 다이나믹 프로그래밍으로 풀이하였다.
• 점화식은 다음과 같다.

  DP[N][T] : 시간이 T이고 해당 노드가 N일때, 이후 목적지까지 최소 수정 갯수
  DP[N][T]

  • 모든 인접한 노드에 대하여 아래 반복
    - 인접 노드가 해당 시간에 맞는 노드면 MIN(DP[N][T], DP[next][T+1])
    - 인접 노드가 해당 시간에 맞지않는 노드면 MIN(DP[N][T], DP[next][T+1] + 1)

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N, M, K, INF = 987654321;
    public List<List<Integer>> map = new ArrayList<>();
    public int[][] dp;
    public int[] move;

    //현재 시점 이후로부터 도달할 때까지 최소 수정 횟수 리턴
    public int solve(int n, int t) {
        //기저 조건 : 마지막에 도착점에 도달했을 때
        if (t == K - 1) {
            if (n == move[t])
                return 0;
            else
                return INF;
        }
        if (dp[n][t] != -1)
            return dp[n][t];

        int result = INF;
        //인접한 모든 노드에 대해 반복
        for (int i = 0; i < map.get(n).size(); i++) {
            int next = map.get(n).get(i);
            if (move[t + 1] != next)
                result = Math.min(result, solve(next, t + 1) + 1);
            else
                result = Math.min(result, solve(next, t + 1));
        }

        return dp[n][t] = result;
    }

    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
        //초기화
        N = n;
        M = m;
        K = k;
        move = gps_log;
        dp = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
            map.add(new ArrayList<>());
            Arrays.fill(dp[i], -1);
        }
        for (int i = 0; i < edge_list.length; i++) {
            int from = edge_list[i][0];
            int to = edge_list[i][1];
            map.get(from).add(to);
            map.get(to).add(from);
        }
        //dp 진행
        int res = solve(move[0], 0);
        if (res == INF) return -1;
        else return res;
    }
}