출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

핵심 개념

1. DP(dynamic programming)
2. edgeMap 만들기

팁

여기서 주목하셔야할 문제 조건은 k값이 충분히 작고, Node 번호들이 연속적이라는 겁니다.
따라서 아래처럼 DP를 작성하시고 문제를 푸시면 좋습니다.
dp[i][j] = Node의 i번쨰 값이 j이고 i번째까지 경로가 valid할 때 수정의 최소 횟수

다만 DP를 채울 때 다음 노드 값을 (1, N) 모두를 고려하는 건 비효율적입니다.
※ i번 째일 때 EdgeMap을 활용해 i+1의 노드 값을 가지치기 할 수 있었습니다.

이미 dp[i][j]가 INF이면 그 다음 값을 구하는 건 크게 의미가 없습니다.

그림 설명

시간 효율성

Initialize 과정: O( (m * 2) + (k * n) )
dynamic programming 과정: O( k(n + m) )

Code:

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = Integer.parseInt(sc.nextLine());
    int m = Integer.parseInt(sc.nextLine());

    int[][] edge_list = new int[m][2];
    String tmpLine = sc.nextLine();
    String[] tmp = tmpLine.substring(1, tmpLine.length() - 1).split("\\],\\[");
    for (int i = 0; i < tmp.length; i++) {
      String[] tt = tmp[i].split(", ");
      edge_list[i][0] = Integer.parseInt(tt[0]);
      edge_list[i][1] = Integer.parseInt(tt[1]);
    }

    int k = Integer.parseInt(sc.nextLine());

    int[] gps_log = new int[k];
    String tempLine = sc.nextLine();
    String[] temp = tempLine.substring(1, tempLine.length() - 1).split(", ");
    for (int i = 0; i < temp.length; i++) {
      gps_log[i] = Integer.parseInt(temp[i]);
    }

    int answer = new Solution().solution(n, m, edge_list, k, gps_log);
    System.out.println(answer);
    sc.close();
  }
}

class Solution {

  public void initializeDP(int[][] dp, int inf) {
    for (int r = 0; r < dp.length; r++) {
      Arrays.fill(dp[r], inf);
    }
  }

  public void initializeEdgeMap(int[][] edge_list,
                                Map<Integer, ArrayList<Integer>> edgeMap) {
    for (int i = 0; i < edge_list.length; i++) {
      int v1 = edge_list[i][0];
      int v2 = edge_list[i][1];

      if (edgeMap.get(v1) == null)
        edgeMap.put(v1, new ArrayList<Integer>());
      if (edgeMap.get(v2) == null)
        edgeMap.put(v2, new ArrayList<Integer>());

      edgeMap.get(v1).add(v2);
      edgeMap.get(v2).add(v1);
    }
  }
  public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
    final int INF = 100000;
    int Min = INF;

    Map<Integer, ArrayList<Integer>> edgeMap =
        new Hashtable<Integer, ArrayList<Integer>>();
    initializeEdgeMap(edge_list, edgeMap);

    int[][] dp = new int[k][n + 1];
    initializeDP(dp, INF);

    int start = gps_log[0];
    int end = gps_log[k - 1];
    dp[0][start] = 0;

    for (int index = 0; index < k - 1; index++) {

      for (int node = 1; node < n + 1; node++) {
        if (dp[index][node] == INF)
          continue;

        ArrayList<Integer> nextCandidates = new ArrayList<>(edgeMap.get(node));
        nextCandidates.add(node);

        for (int nextNode : nextCandidates) {
          int value = dp[index][node];

          if (nextNode != gps_log[index + 1])
            value++;

          dp[index + 1][nextNode] = Math.min(dp[index + 1][nextNode], value);
        }
      }
    }

    return ((dp[k - 1][end] != INF) ? dp[k - 1][end] : -1);
  }
}