[프로그래머스 - Level3] GPS

전체 문제 설명

문제 요약

택시는 거점을 이동해 다니며, 거점 간의 링크, 택시 운행 기록이 변수로 주어집니다.
그런데 운행기록 gps_log의 정보에는 일부분 오류가 있습니다.(이동 불가능한 경로로 이동함)
gps_log의 첫 번째, 그리고 마지막 값은 고정한 채로, 나머지 기록들을 수정해서 적절한 이동 경로를 만들 수 있는, 최소의 오류 수정 횟수를 구하는 문제입니다.

해결을 위한 접근

우선, 첫 번째와 마지막 값은 고정해야 됩니다.
운행기록의 길이가 k라고 하고 마지막 기록(k번째로 방문한 거점 정보)이 고정되었을 때, gps_log가 적절한 이동경로가 되기 위해서는,
(k - 1)번째로 방문한 거점과 k번째로 방문한 거점이 연결되어 있어야 할 것입니다.
k번째 방문 거점은 고정된 정보이니, (k - 1)번째 방문 거점이 될 수 있는 후보군을 추려낼 수 있습니다.

만약 거점간 연결이 위와 같은 형태이고, k번째로 방문한 거점이 7번 거점이라면, k - 1번째로 방문 거점은 반드시 5, 6 혹은 7번이어야 합니다.
(택시는 이동하지 않고 제자리에 머물 수도 있습니다.)

이제, 이 문제의 해는 k - 1번째로 방문한 거점이 5인 경우, 6인 경우, 혹은 7인 경우의 최적해(각 경우의 최소 오류 수정 횟수) 중 최솟값으로 정의할 수 있습니다. 각 부분 문제에 대해서는 다시 k - 2번째로 방문한 거점이

(3, 5, 6, 7) -> 5
(4, 5, 6, 7) -> 6
(5, 6, 7)    -> 7

인 경우의 최적해 + α로 나누어 생각할 수 있겠네요. k - 1번째 거점이 gps_log의 정보와 대응된다면 α는 0이고, 그렇지 않다면 오류 수정을 한 것이므로 α는 1이 됩니다.

이를 조금 더 일반화 시키면, (1 <= i <= k)인 i에 대해서 i번째 방문 노드를 j로 만들 때의 최적해는

1. i번째 방문 노드가 gps_log[i]와 같은 경우
   (i - 1) 번째 방문노드를 x로 만들었을 때의 최적해
   
   
2. i번째 방문 노드가 gps_log[i]와 다른 경우
   1. 에서 구한 최적해 + 1

입니다.

따라서, gpslog의 길이가 k이고 거점의 개수가 n일 때,
i (1 <= i <= k) 번째 방문 거점을 j (1 <= j <= n) 로 만들 때의 최적해를 각각 구해야 하고,
각 단계에서 i - 1번째 거점이 x(j와 연결된 거점)일 때의 최적해를 참고해야합니다.

다음과 같은 2차원 배열을 정의해서 문제를 풀어나갈 수 있습니다.

dp[i][j]: i번째 방문 거점이 j가 되는 경우의 최적해
(해가 존재하지 않는다면 = i번째 방문 거점이 j일 때 유효한 경로가 존재하지 않는다면 INF)

이 방법으로 접근했을 때의 코드는 다음과 같이 작성할 수 있습니다.

import java.util.*;
class Solution {
    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
            int answer = -1;
            int[][] dp = new int[k][n + 1];
            List<Integer>[] edges = new List[n + 1];
            for(int i = 0; i <= n; i++) {
                edges[i] = new LinkedList<>();
                edges[i].add(i);
            }
            for(int i = 0; i < k; i++){
                Arrays.fill(dp[i], Integer.MAX_VALUE);
            }
            dp[0][gps_log[0]] = 0;
            for(int[] edge : edge_list){
                edges[edge[0]].add(edge[1]);
                edges[edge[1]].add(edge[0]);
            }

            for(int i = 1; i < k; i++){
                for(int j = 1; j <= n; j++){
                    for(Integer linkedTaxiStop : edges[j]){
                        if(dp[i - 1][linkedTaxiStop] == Integer.MAX_VALUE) continue;

                        dp[i][j] = Math.min(dp[i][j], gps_log[i] == j? dp[i - 1][linkedTaxiStop] : dp[i - 1][linkedTaxiStop] + 1);
                    }
                }
            }


            answer = dp[k - 1][gps_log[k - 1]];
            return answer == Integer.MAX_VALUE? -1 : answer;
    }

}

이 방식으로 문제를 해결하는 경우 O(k(n + m))의 시간 복잡도를 가집니다.

다른 접근법

위에서는 각 단계 i에 대해, i번째 방문 거점이 j가 되었을 때의 최적해를 구하는 방식으로 부분문제를 정의하고 2차원 배열을 이용하여 활용하여 이를 해결했습니다.
한편, 다른 관점으로도 접근할 수 있습니다.
다음과 같이 부분문제를 정의해 보면 어떨까요

dp[i] : i번째 방문 거점을 도착지점으로 간주했을 때의 최적해

gps_log의 i번째 방문 기록이 7번 거점이라고 가정해 보겠습니다.


i번째 방문 거점인 7번을 도착지점으로 가정했을 때, i번째 방문 기록으로부터 앞으로 연속된 0개의 기록을 수정할 수도 있고,

아래와 같이 2개의 연속된 기록을 수정할 수도 있습니다.
(0개부터 시작과 종점을 뺀, i - 2개 까지 고려해 볼 수 있습니다.)

당연한 소리지만, 각 경우에 대해서, i - 1번째와 i - 3번째 값은 변하지 않습니다.
(case 1에서 i - 1번째 값을 수정하게 되면 연속된 0개의 기록을 수정한 게 아닌 1개의 기록을 수정한 아예 다른 case가 되고, case 2에서 i - 3번째 값을 수정하게 되면 연속된 3개의 기록을 수정한 다른 case가 됩니다.)

그렇다면, case 1에서는 i - 1번째 값이 변하지 않으므로, i - 1번째 값을 도착지점으로 하는 부분 최적해가 곧 i번째 방문지점까지 고려한 더 큰 부분 문제의 해답이 된다고 생각할 수 있습니다.
case 2에서는 i - 3번째 값을 도착지점으로 하는 부분 최적해에 2를 더한 값이 i번째 방문지점까지 고려한 부분 문제의 해답이 됩니다.

처음에 언급한 것처럼 i로부터, 연속된 0개 ~ (i - 2)개까지 수정한 case를 고려할 수 있지만, 그중 유효하지 않은 경우들은 제외시켜야 합니다. 예를 들어, i로부터 0개의 기록을 지우는 case를 가정했는데 i - 1과 i 사이에 링크가 없다면 이는 유효한 case가 아닙니다.
마찬가지로, i로부터 2개의 기록을 지우는 case를 가정한다면, i - 3번째로 방문한 노드와 i번째 노드는 3번의 이동 안에 도착할 수 있는 거리에 위치해야 합니다.

이 접근법을 이용해 gps_log의 i번째 값이 도착지점일 때의 부분 최적해를 구하는 과정을 더 구체화하자면 다음과 같습니다.

(0 <= j <= i - 1) 인 j에 대해
1. i와 j가 ( i - j )의 거리 이내에 위치해 있는지 검증한다.
(아니라면 유효하지 않은 case)

2. j를 도착지점으로 삼는 유효한 부분해가 존재하는지 검증한다.
(j를 도착지점으로 하는 올바른 부분경로가 만들어질 수 없다면 INF - 유효하지 않은 case)

3. 1, 2단계의 검증을 통과한다면 (i - j + 1)(i - 1부터 수정한 연속된 기록의 갯수)과 j를 도착지점으로 하는 부분 최적해의 합이 i를 도착지점으로 하는 더 큰 부분문제의 해 후보가 된다.

코드로는 다음과 같이 표현될 수 있습니다.

for(int i = 1; i < k; i++){
    min = Integer.MAX_VALUE;
    for(int j = i - 1; j >= 0; j--){
    	dist = i - j;
    	//i - j이하의 거리로 이동 불가능하거나, j번째 log를 바꾸지 않을 시 올바른 경로가 되지 않는 경우
    	if(d[gps_log[i]][gps_log[j]] > dist || optVal[j] == -1) continue;
        
       	//부분 최적해 후보
        min = Math.min((dist - 1) + optVal[j], min); 
    }
    if(min != Integer.MAX_VALUE) optVal[i] = min;
}

여기서 조금 더 효율적으로 수정하기 위해, 굳이 j를 1씩 감소시키지 않고 필요한 만큼 감소시도록 변경할 수 있습니다.

부분 최적해를 구하고 갱신하는 코드는 이 부분인데,

min = Math.min((dist - 1) + optVal[j], min);

부분 최적해가 될 수 있는 값을 찾았음에도 for루프를 돌며 j를 계속 감소시키는 이유는, i로부터의 연속된 수정횟수(dist - 1)를 더 늘리더라도, optVal[j](j를 도착지점으로 하는 부분 최적해)의 값이 그 이상으로 낮아지는 지점이 발생할 수 있기 때문입니다.

즉, optVal이 변하는 가장 가까운 지점을 기록해 놓는다면 j를 1씩 감소시키지 않고, optVal이 변하는 지점으로 점프시킬 수 있습니다.

여기에 더해, optVal이 설사 0이 되더라도 지금의 최적해 후보 min보다 낮아질 수 없는 경우라면 탐색을 중단하고 다음 단계로 진행하는 것이 효율적입니다.

for(int i = 1; i < k; i++){
    min = Integer.MAX_VALUE;
    nearChangePoint[i] = nearChangePoint[i - 1]; //optVal이 변하는 가장 가까운 지점

    for(int j = i - 1; j >= 0;){
        dist = i - j;
        //i - j이하의 거리로 이동 불가능하거나, j번째 log를 바꾸지 않을 시 올바른 경로가 되지 않는 경우
        if(d[gps_log[i]][gps_log[j]] > dist || optVal[j] == -1) {j--; continue;} 

        min = Math.min((dist - 1) + optVal[j], min); //부분 최적해 후보

	//optVal이 변하는 지점이 없는 경우
        if(nearChangePoint[j] == -1) break;
        //optVal이 변하는 지점까지 j를 이동시켰을 때, min값보다 더 작은 해를 구할 수 없는 경우 
        if( (i - nearChangePoint[j] - 1) >= min ) break;

        j = nearChangePoint[j];
    }
    if(min != Integer.MAX_VALUE) optVal[i] = min;
    if(optVal[i] != optVal[i - 1]) nearChangePoint[i] = i - 1;
}

이 방식으로 문제를 해결하기 위해서 우선, 각 거점 사이의 최단 경로 d[i][j]가 구해져 있어야 합니다.
간선의 가중치가 없으므로 BFS를 통해서 O(n^2)의 시간으로 모든 거점 사이의 최단거리를 구할 수 있습니다. 이 접근법으로 해결한 전체 코드는 다음과 같습니다.

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

    int[][] d = new int[n + 1][n + 1];
    int[] optVal = new int[k];// 0부터 i번째 까지 고려했을 때 구할 수 잇는 최소 오류 수정 횟수
    int[] nearChangePoint = new int[k]; //optVal, 즉 부분 최적해의 값이 달라지는 가장 가까운 지점
    Arrays.fill(nearChangePoint, -1);
    Arrays.fill(optVal, - 1);
    List<Integer>[] edges = new List[n + 1];

    for(int[] arr : d){
        Arrays.fill(arr, Integer.MAX_VALUE);
    }
    for(int i = 1; i <= n; i++){
        d[i][i] = 0;
        edges[i] = new LinkedList<>();
    }

    for(int[] e : edge_list){
        edges[e[0]].add(e[1]);
        edges[e[1]].add(e[0]);
    }
    setShortestDist(d, edges);
    
    optVal[0] = 0;
    int min, dist;

    for(int i = 1; i < k; i++){
        min = Integer.MAX_VALUE;
        nearChangePoint[i] = nearChangePoint[i - 1];

        for(int j = i - 1; j >= 0;){
            dist = i - j;
            //i - j이하의 거리로 이동 불가능하거나, j번째 log를 바꾸지 않을 시 올바른 경로가 되지 않는 경우
            if(d[gps_log[i]][gps_log[j]] > dist || optVal[j] == -1) {j--; continue;} 

            min = Math.min((dist - 1) + optVal[j], min); //부분 최적해 후보

            if(nearChangePoint[j] == -1) break;
            if( (i - nearChangePoint[j] - 1) >= min ) break;

            j = nearChangePoint[j];
        }
        if(min != Integer.MAX_VALUE) optVal[i] = min;
        if(optVal[i] != optVal[i - 1]) nearChangePoint[i] = i - 1;
    }

    return optVal[k - 1];
}
private void setShortestDist(int[][] d, List<Integer>[] edges) {
    Queue<Integer> q = new LinkedList<>();
    Integer node;   
    int qSize, depth;

    for(int i = 1; i < d.length; i++){
        q.clear();
        q.add(i);
        depth = 0;

        while (!q.isEmpty()) {
            qSize = q.size();
            depth++;
            for(int j = 0; j < qSize; j++){
                node = q.poll();

                for(Integer n  : edges[node]){
                    if(d[i][n] != Integer.MAX_VALUE) continue;

                    d[i][n] = depth;
                    q.offer(n);
                }
            }
        }
    }
}

이러한 방식의 해결의 경우 최단거리를 구하는데 O(n^2), 최적해를 계산하는 데 최악의 경우 O(k^2)이 걸립니다.