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

목차

1. 문제
2. 문제 조건
3. 문제 조건 분석
4. 알고리즘
5. 코드

문제

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

문제 조건

택시의 총 시간대: 2<=k<=100
거점 개수: n개

문제 조건 분석

총 100초에 대해 200개의 거점을 backTracking으로 간다고 가정하는 것이 제일 베이직한 풀이이다. (정답 도출 위해 가지치기 필수)

이렇게 따지면 200*^100으로 매우 높은 시간 복잡도가 도출되게 된다.

-> 가지치기와 DP를 도입함으로써 시간 복잡도를 줄이자!

알고리즘

도착 초부터 시작 초까지 depth를 내려가며 메모이제이션을 통해 총 수정횟수를 확인한다. 도착할 수 없는 경우도 존재하기 때문에 이도 고려한다.

코드

import java.util.*;

class Solution {
    static int[][] dp;
    
    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {     
        //dp 초기화
        dp = new int[k][n+1];
        for(int i=0;i<k;i++){
            Arrays.fill(dp[i], -1);
        }
        
        List<Integer>[] maps = new List[n+1];
        for(int i=1;i<=n;i++){
            maps[i] = new ArrayList<>();
            maps[i].add(i);
        }
        
        for(int[] edge:edge_list){
            int a = edge[0];
            int b = edge[1];
            
            maps[a].add(b);
            maps[b].add(a);
        }
        
        int res = backTracking(k-1, gps_log, maps, gps_log[k-1]);
        return res == Integer.MAX_VALUE?-1:res;
    }
    
    private int backTracking(int depth, int[] gps_log, List<Integer>[] maps, int now){
        if(dp[depth][now]!=-1){
            return dp[depth][now]; //dp[깊이][현재경로] 의 최단수정 
        }
        
        //종료조건
        if(depth == 0){
            if(now != gps_log[0]){
                //도착할 수 없는 경우
                return Integer.MAX_VALUE;
            } else {
                return 0;
            }
        }
        
        int min = Integer.MAX_VALUE;
        for(int conn:maps[now]){
            int res = backTracking(depth-1, gps_log, maps, conn);
            
            min = Math.min(min, res);
        }
        
        if(gps_log[depth] != now && min!=Integer.MAX_VALUE){
            min++;
        }
        
        dp[depth][now] = min;
        return min;
    }
}