문제

https://school.programmers.co.kr/learn/courses/30/lessons/1837?language=java

풀이

dp로 풀었습니다.
원래는 dp와 재귀 함수를 섞어서 막 이상하고 복잡하게 풀었었는데 통과하고 나서 다른 분들 풀이를 보니 더 나은 풀이법이 있어 다시 한번 풀어봤습니다.

준비

		//dp[순서][거점] -> 택시가 해당 이동 순서 때/ 해당 거점에 도달하는 데 필요한/ 최소 경로 수정 횟수.
        // 0이면 도달 못한 거. 1 이상이면 -1 한게 필요한 최소 경로 수정 횟수
        int dp[][] = new int[k][n];
        List<Set<Integer>> edgeList = new ArrayList<>();

사용할 dp입니다.
dp[A][B]는 택시가 순서 A일때 거점 B에 도달하기 위해 필요한 최소 경로 수정 횟수를 의미합니다.

도달하지 못한 경우를 -1로 두면 더 직관적이긴 할텐데 초기화가 귀찮아서 0으로 두었습니다. dp[A][B]가 0일 경우 해당 순서에 해당 거점에 도달할 수 있는 방법은 없다는 뜻이며, 다른 숫자면 1을 뺀 값이 필요한 최소 수정 횟수입니다.

edgeList는 거점과 연결된 다른 거점을 정리한 리스트입니다. 관계가 중복해서 주어질 것 같진 않지만 혹시나 해서 Set으로 두었습니다.

DP 쌓기

		dp[0][gps_log[0]-1] = 1;
        
        for(int i = 0; i < k-1; i++){
            for(int j = 0; j < n; j++){
                if(dp[i][j] == 0){
                    continue;
                }
                
                for(int v : edgeList.get(j)){
                    int cost = dp[i][j];
                    if(gps_log[i+1]-1 != v){
                        cost++;
                    }
                    
                    dp[i+1][v] = dp[i+1][v] == 0 ? cost : Math.min(dp[i+1][v], cost);
                }
            }
        }
        
        int answer = dp[k-1][gps_log[k-1]-1] - 1;

출발 지점을 1로 세팅한 후 시작합니다.

k-1(주어진 순서-1)만큼 루프를 돌면서

i 순서에 j 거점에 도달할 수 있는 지 확인합니다.
(dp[i][j]이 0이 아니면 도달할 수 있다)

도달할 수 있으면 j 거점과 연결된 모든 거점 v와 다음 순서(i+1)에 연결합니다.
dp[i+1][v]가 0이면 연결된 적 없었으니 바로 값을 갱신해 주면 되고 0이 아니면 갱신할 값과 원래 있는 값 중 최솟값을 선택하면 됩니다.

갱신할 값은 거점 v까지 도달하는 데 필요한 최소 수정 횟수인 dp[i][j]이며, gps_log[i+1] -1값이 v와 다르면, 즉 다음 순서에도 gps 수정이 필요하면 값에 1을 더해줍니다.

거점 개수가 적어서 for문을 돌렸지만 j 쪽을 Set로 구현하면 좀 더 나을 것 같기두.

전체 코드

import java.util.*;
// 통과하긴 했는데 코드가 엉망이어서 다른 사람 풀이 참고해서 다시 ㄱ

class Solution {
    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
        //dp[순서][거점] -> 택시가 해당 이동 순서 때/ 해당 거점에 도달하는 데 필요한/ 최소 경로 수정 횟수.
        // 0이면 도달 못한 거. 1 이상이면 -1 한게 필요한 최소 경로 수정 횟수
        int dp[][] = new int[k][n];
        List<Set<Integer>> edgeList = new ArrayList<>();
        
        for(int i = 0; i < n; i++){
            edgeList.add(new HashSet<>());
            edgeList.get(i).add(i);
        }
        
        for(int[] edge : edge_list){
            edgeList.get(edge[1]-1).add(edge[0]-1);
            edgeList.get(edge[0]-1).add(edge[1]-1);
        }
        
        dp[0][gps_log[0]-1] = 1;
        
        for(int i = 0; i < k-1; i++){
            for(int j = 0; j < n; j++){
                if(dp[i][j] == 0){
                    continue;
                }
                
                for(int v : edgeList.get(j)){
                    int cost = dp[i][j];
                    if(gps_log[i+1]-1 != v){
                        cost++;
                    }
                    
                    dp[i+1][v] = dp[i+1][v] == 0 ? cost : Math.min(dp[i+1][v], cost);
                }
            }
        }
        
        int answer = dp[k-1][gps_log[k-1]-1] - 1;
        return answer;
    }
}