[ 프로그래머스 / Programmers Level 3 ] GPS

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

코딩테스트 연습 - GPS

 

문제 설명

---

카카오 택시 개발자 Jay-G는 다음 업데이트를 준비하기 위해 개선사항을 위한 여러 피드백을 받았다. 그중에서 손님이 자주 탑승하는 위치를 추천해주었으면 한다는 의견이 많았다.

다음 업데이트 준비를 위해 Jay-G는 택시의 승하차 및 이동 경로를 수집하여 분석하기 시작하였다. 데이터를 분석하던 Jay-G는 몇 가지 특이사항을 발견했다. 택시의 이동 경로를 GPS를 통해 수집하게 되는데, GPS 신호 불량, 통신 오류 등 다양한 원인으로 위치의 오류가 발생한 것을 알게 되었다. 다만 승차 위치와 하차 위치는 오류가 없는 것으로 확인이 되었다. 

개발자 Jay-G는 수집한 이동 경로의 오류를 최소한으로 수정하여 좀 더 정확한 이동 경로를 구하고 싶어 한다.

택시는 다음과 같은 조건으로만 이동한다. 먼저 택시는 거점을 이동해 다니며, 거점 간의 이동은 해당하는 도로가 있는 경우에만 가능하다. 또한, 교통 상황에 따라 택시는 한 거점에 머무를 수 있고, 왔던 길을 되돌아갈 수 있다. 모든 도로는 방향이 별도로 없는 왕복 도로이다.

예를 들어, 위 그래프에서 택시가 다음과 같이 시간대별로 이동 경로를 보내왔다. 

t	위치
1	1
2	2
3	3
4	3
5	6
6	7

하지만 위의 택시가 보내온 경로에는 거점 3에서 거점 6으로 이동할 수 있는 도로가 없으므로 이동 경로에 오류가 있다. 

이러한 오류를 최소한으로 수정하여 이동 가능한 경로로 만들고 싶다. 이 경우 1회의 오류를 수정하여 다음과 같이 이동 가능한 경로를 만들 수 있다. 시간 t=4의 위치를 거점 5로 한 번 수정하면 이동 가능한 경로가 된다. 

t	위치
1	1
2	2
3	3
4	5
5	6
6	7

 

이와 비슷하게 시간 t=4의 위치를 거점 4로 바꾸거나, 시간 t=5 위치를 거점 5로 바꾸면 이동 가능한 경로로 만들 수 있다. 위의 경우 수정한 오류의 개수는 1개이다. 

t	위치
1	1
2	2
3	3
4	4
5	6
6	7

 

t	위치
1	1
2	2
3	3
4	3
5	5
6	7

 

위와 같이 택시가 보내온 경로에서 이동 가능한 경로로 만드는 최소의 오류 수정 횟수를 구하여라.

 

입력 형식

---

주어지는 입력은 총 다섯 가지로, 거점 개수 n과 도로의 개수 m, 각 거점 간의 연결된 도로 정보 edge_list, 택시가 시간대별로 보내오는 거점 정보의 총 개수 k, 그리고 머물렀던 거점의 정보 gps_log이다. 제한조건은 아래와 같다.

• 2 <= n <= 200
• 1 <= m <= 10,000
• 2 <= k <= 100
• edge_list는 m × 2 크기의 2차원 배열로, 각 행의 두 값은 도로가 잇는 두 거점의 번호를 의미한다.
• 거점의 번호는 1부터 n까지 숫자이다.
• 모든 도로는 양방향 통행이 가능하다.
• 입력되는 데이터에서 항상 모든 거점 간 경로가 있음이 보장되지 않는다.
• gps_log의 시작 거점과 도착 거점은 바뀔 수 없다.

 

출력 형식

---

이동 가능한 경로로 만들 수 있는 최소의 오류 수정 횟수를 리턴한다. 올바른 경로로 수정하는 것이 불가능할 경우 -1을 리턴한다.

 

풀이

---

아씨....🤦‍♀️

너무 어려워써.... 그래서 다른 사람들의 설명을 많이 참조해서 해결ㄷ했다....

나에겐 너무 어려운 DP🥶

 

dp[i][j] 👉 gps_log의 i 번째 인덱스에 j 거점이 온다면 0번 인덱스부터 i 번 인덱스까지 총 변한 최소 수

         1️⃣  j 거점과 연결된 거점으로 이동하는 경우

         2️⃣ 이동하지 않는 경우

 

두 가지 모두 확인해서 최소값을 찾고, 

gps_log [i] 가 현재 거점 j 와 일치하지 않으면 바꿔줘야하므로 +1 해주었다.

 

코드

---

import java.util.ArrayList;
import java.util.List;

public class GPS {

    static int INF = 999999999;

    public static int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {

        List<Integer>[] adj = new List[n+1];
        int[][] dp = new int[k][n+1];

        for(int i = 0 ; i < n+1; i++){
            adj[i] = new ArrayList<>();
        }
        for(int i = 0 ; i < edge_list.length ; i++){
            int o = edge_list[i][0];
            int t = edge_list[i][1];
            adj[o].add(t);
            adj[t].add(o);
        }

        for(int i = 0 ; i < k ; i++){
            for(int j = 0 ; j < n+1 ; j++){
                dp[i][j] = INF;
            }
        }

        // 맨 처음 거점은 정해져 이씀
        dp[0][gps_log[0]] = 0;

        for(int i = 1 ; i < k ; i++){
            for(int j = 1 ; j < n+1; j++){
                // 이동 x
                dp[i][j] = Math.min(dp[i][j], dp[i-1][j]);

                // 인접한 노드로 이동을 하는 경우
                for(int next : adj[j]){
                    dp[i][j] = Math.min(dp[i-1][next], dp[i][j]);
                }

                // gps_log[i]와 현재 거점이 일치하지 않으면 변경되었음
                if(j != gps_log[i])
                    dp[i][j]++;
            }
        }

        if(dp[k-1][gps_log[k-1]] < INF)
            return dp[k-1][gps_log[k-1]];

        return -1;
    }

    public static void main(String[] args) {
        int[][] edge_list = {{1,2} , {1,3}, {2,3}, {2,4}, {3,4}, {3,5}, { 4,6}, {5,6} , {5,7}, {6,7}};
        int[] gps_log = {1,2,3,3,6,7};

        System.out.println(solution(7, 10, edge_list, 6, gps_log));
    }

}