[프로그래머스/Java] [2017 카카오코드 본선] GPS

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1837

프로그래머스

 

 

🔍  해결 과정

이 문제는 결론적으로 dp를 활용하여 해결할 수 있는 문제입니다.

문제에서 k초 동안의 각 거점의 경로가 주어지는데 이 점을 활용하여 dp의 정의를 다음과 같이 생각할 수 있습니다.

dp[t][v]: t초에 v지점에 위치했을 때 필요한 최소 수정 횟수

 

문제의 예시에서 gps_log와 dp의 관계를 기준으로 설명하겠습니다. 

 

먼저 dp의 초기값들은 이동한 경로 정보가 없으므로 INF(Infinity)로 초기화를 해줍니다.

gps_log에서 처음에 등장하는 노드와 마지막에 등장하는 노드는 오류가 아니라고 문제에서 명시를 했으므로 gps_log에서 처음에 나오는 노드값에 대해서 수정횟수는 필요 없습니다. 따라서 0으로 수정하고 dp의 결과를 보면 다음과 같습니다.

dp = [0 INF INF INF INF INF INF]                // k = 1
         [INF INF INF INF INF INF INF]            // k = 2
         [INF INF INF INF INF INF INF]            // k = 3
         [INF INF INF INF INF INF INF]            // k = 4
         [INF INF INF INF INF INF INF]            // k = 5
         [INF INF INF INF INF INF INF]            // k = 6

 

dp에서 각각의 열이 의미하는 것은 노드의 번호를 의미합니다.

예시 1에서는 gps_log에서 초기 경로 노드는 1이므로 k = 1에서 1번 노드일 때 수정 횟수가 필요 없음을 명시했습니다.

 

그래프를 활용하여 dp에서 INF를 제외한 노드에서 서로 연결되어 있는 노드를 차례대로 뽑아가며 gps_log와 비교하며 다음 경로의 노드에 대해서 필요한 최소 수정 횟수를 카운트하면서 dp의 내용을 수정해주면 됩니다. 그림으로 설명하겠습니다.

 

먼저 k = 1은 노드 시작점이므로 수정 횟수를 0으로 처리합니다. 그리고 해당 노드와 연결된 노드는 문제의 그래프에 따라서 2번과 3번 노드이므로 이 둘의 노드를 다음 경로로 선택했을 때의 상황으로 넘어갑니다. 여기서 또 처리해야 할 것이 있는데 문제에서 자기 자신에서 머무르기도 가능하므로 실질적으로는 1번, 2번, 3번 노드를 전부 살펴보아야 합니다. gps_log에서 k = 2일 때의 node는 2이므로 dp에서 다음 경로를 담고 있는 행에서의 정보를 수정하면 다음과 같습니다.

k = 2 부분에서의 dp를 보시면 1번 노드와 3번 노드는 gps_log와 경로상 일치하지 않으므로 수정이 한 번 필요합니다. 따라서 1번과 3번 자리에서의 값은 1입니다.

 

k = 3일 때의 경우를 살펴봅시다. k = 3에서 gps_log의 노드값은 3이므로 해당 노드 번호와 일치하는지 안하는지에 따라서 필요한 수정횟수가 dp에서 달라질 것입니다. 결론적으로 k = 3 자리에서 dp의 값은 다음과 같습니다.

 

k = 3을 기준으로 봤을 때 gps_log 경로에 따라 k = 3에서 1번, 2번, 4번 경로를 표기했다면 최소 한 번의 수정이 필요하다는 의미이고, 5번 노드라면 최소 두 번의 수정이 필요하다는 의미가 됩니다.

 

5번 노드는 왜 두 번의 수정이 필요할까?

gps_log에서 k = 1부터 3까지의 경로를 표현하면 1 -> 2 -> 3 입니다.

그런데 그래프에 따라서 세 턴만에 노드 5까지 갈 수 있는 방법은 1 -> 3 -> 5입니다.

애초에 k = 3에서 gps_log 경로와 맞지 않으므로 한 번의 수정은 무조건 필요한 상황이고, 그 중간 경로에서도 3번 노드도 일치하지 않으므로 또 한번의 수정이 필요하므로 최소 수정 횟수가 총 2회가 되는 것입니다.

 

이러한 계산 과정을 더 손쉽게 하기 위해, gps_log를 활용해 특정 시점 노드에서 연결된 노드를 다음 시점의 gps_log와 비교하면서 수정 횟수를 누적하는 방식을 쓸 수 있습니다. 그리고 이를 점화식으로 표현하면 다음과 같습니다:

dp[i + 1][w] = Min(dp[i + 1][w], dp[i][v] + cost) (cost: 수정해야할 횟수)

 

이 점화식을 사용하면 \text{dp} 테이블을 적절히 갱신해, 최종적으로 필요한 최소 수정 횟수를 구할 수 있습니다.

 

 

💬 회고점

걸린시간: 2시간

 

복잡한 문제를 보면 어떤 유형의 문제인지 금방 파악하는 능력이 좀 더 필요함을 느꼈습니다.

앞으로 여러 번 복습해가며 풀어볼 만큼 의미 있는 문제라고 생각했습니다.

 

---

✏️ 코드

import java.util.*;

class Solution {
    
    private static final int INF = (int) 1e9;
    
    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
        List<Integer>[] adj = new ArrayList[n + 1];
        
        initMatrix(adj, n, m, edge_list);
        
        return getMinCorrection(adj, gps_log, n, m, k);
    }
    
    private int getMinCorrection(List<Integer>[] adj, int[] gps_log, 
                                 int n, int m, int k) {
        int[][] dp = new int[k][n + 1];
        
        for (int i = 0; i < k; ++i) {
            Arrays.fill(dp[i], INF);
        }
        
        dp[0][gps_log[0]] = 0;
        
        for (int i = 0; i < k - 1; ++i) {
            for (int v = 1; v <= n; ++v) {
                if (dp[i][v] == INF) {
                    continue;
                }
                
                if (i + 1 == k - 1) { // 경로 끝이라면
                    int w = gps_log[k - 1];
                    
                    if (adj[v].contains(w)) {
                        dp[i + 1][w] = Math.min(dp[i + 1][w], dp[i][v]);
                    }
                } else {
                    for (int w : adj[v]) {
                        int cost = dp[i][v];
                        
                        if (gps_log[i + 1] != w) {
                            ++cost;
                        }
                        
                        dp[i + 1][w] = Math.min(cost, dp[i + 1][w]);
                    }
                }
            }
        }
        
        int result = dp[k - 1][gps_log[k - 1]];
        
        if (result >= INF) {
            result = -1;
        }
        
        return result;
    }
    
    private void initMatrix(List<Integer>[] adj, int n, int m, int[][] edge_list) {
        
        for (int i = 0; i <= n; ++i) {
            adj[i] = new ArrayList<>();
        }
        
        // 자기 자신에서 머무르는 경우도 고려
        for (int i = 1; i <= n; ++i) {
            adj[i].add(i);
        }
        
        for (int i = 0; i < m; ++i) {
            int a = edge_list[i][0], b = edge_list[i][1];
            adj[a].add(b);
            adj[b].add(a);
        }
        
    }
}