[2017 카카오코드] GPS for JAVA

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의 시작 거점과 도착 거점은 바뀔 수 없다.

 

[풀이]

문제에서는 결론만 물어본다. 과정을 반환하는 것이 아니라, 출발점과 도착점은 오류가 나지 않고 중간 과정의 최소한의 오류 수정 횟수만 물어본다. 어느 부분에서 최소화의 경로나 경유 등을 찾을 때는 주로 DP를 사용한다. 이 문제도 DP로 접근했다.

예시

위는 경로가 1 2 3 4 5 6 7 순이고 마주한 도시들이 서로 연결돼있을 때 나올 수 있는 예시이다. 

 

만약 경로가 1 2 3 4 4 6 7이라면?

 

 

4와 6이 연결이 되지 않았으므로 이런 식으로 중간에 끊길 것이다. 하지만 4와 6이 연결돼있다면,

 

이런 식으로 연결될 것이다.

 

체크를 해야 하는 부분은

1. 현재 택시가 있는 곳은 전 단계에서 정차해서 이전 정점과 같은 곳에 있을 수 있고, 혹은 연결된 모든 정점에서 올 수 있다.

2.  만약 택시가 있는 곳이 gps_log의 경로와 같다면 +0,  아니라면 수정한 것이니 +1

 

[코드]

import java.util.ArrayList;
import java.util.Arrays;
 
public class GPS_DP {
    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
        int answer = 0;
        int inf = 987654321;
        int dp[][] = new int[k][n+1];            //gps_log가 0부터 시작하지 않기때문에 +1을 준다.
        ArrayList<ArrayList<Integer>> al = new ArrayList<ArrayList<Integer>>();
        
        //graph 초기화
        for(int i = 0; i < n + 1; i++) {
            al.add(new ArrayList<Integer>());
        }
        
        //graph 값 넣기
        for(int i = 0; i < edge_list.length; i++) {
            int startNode = edge_list[i][0];
            int endNode = edge_list[i][1];
            
            al.get(startNode).add(endNode);            //양방향 그래프
            al.get(endNode).add(startNode);
        }
        
        for(int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], inf);
        }
        dp[0][gps_log[0]] = 0;
        
        //시작점과 오류가 나지 않기 때문에 1 ~
        for(int i = 1; i < k ; i++) {
            
            //gps_log 숫자 표현상 첫 번째 자리는 안쓰는게 편함.
            for(int j = 1; j < n + 1; j++) {
                
                dp[i][j] = Math.min(dp[i][j], dp[i-1][j]);            //어떻게든 최소 오류수정만 있으면 되므로 & 택시가 정차한 경우
                
                for(int node : al.get(j)) {
                    dp[i][j] = Math.min(dp[i-1][node], dp[i][j]);    //자신과 연결된 정점 중 어디서 온것이 가장 적은 오류수정 횟수인지 판단
                }
                
                dp[i][j] += gps_log[i] == j ? 0 : 1;                //지금 최소 오류 수정 루트를 찾고있는 j의 도시가 gps_log가 정해준 도시와 맞는지
            }
        }
        
        if(dp[k - 1][gps_log[k - 1]] >= inf) {
            answer = -1;
        }else {
            answer = dp[k-1][gps_log[k -1]];
        }
        
        
        
        return answer;
    }
}

 

느낀 점 : 처음에는 dfs로 풀었다. 틀린 부분에서만 dfs로 탐색하려고 했다. 이유는 모르겠지만 테스트 케이스만 통과하고 채점에서는 통과를 못했다. 구글 검색을 통해 다른 분이 작성한 코드를 보니 dp로 작성하는 게 더 효율적이고 쉽다는 것을 알았다. dp가 자주 사용되는 상황을 깊게 이해하고 있어야겠다.