이번 문제는 프로그래머스의 GPS 문제이다.
2017 카카오코드 본선 문제라는데… 어떤 대회인 것 같다.
문제를 차근차근 읽어보도록 하자.

최대 200개의 거점과 10,000개의 도로가 주어진다.
택시가 시간대 별로 보내오는 거점의 로그는 최대 100개 이다.
또한 10,000개의 도로에 대해 정보가 10,000 * 2의 배열로 주어진다.

image

이 때, 위와 같이 없는 경로에 대해 로그가 찍혀있다면, 반드시 수정을 해야 한다.
이동 가능한 경로로 만들 수 있는 최소 수정 횟수를 구하라!
수정이 불가능한 경우에는 -1을 반환하도록 한다.

문제 분석

우선 정점과 간선이 주어지는 것을 보니, 그래프를 만들어야 할 것 같다.
또한 우리가 관심을 가져야 할 것은 GPS 로그이다.
만약 for문을 돌려서 탐색한다면 로그를 가장 먼저 탐색해야 할 것 이다.

완전 탐색?

그럼 최소한의 수정으로 경로를 올바로 만들 수 있음은 어떻게 계산할 수 있을까?
먼저 보통 그래프라면, 실제로 그래프를 탐색해서 모든 경우를 살펴볼 수 있겠다.
하지만 우리가 살펴봐야 하는 정점의 수는 최대 200개이다.
모든 잘못된 경로를 직접 수정하며 백트래킹과 같이 수행한다고 가정해보자.

그럼 잘못된 경로가 10개 있다고 생각했을 때, 최악의 경우 200^10이 된다.
즉 시간초과가 발생할 가능성이 농후하므로, 다른 방법을 사용해야 한다.

DP

보통 최소라는 조건이 들어가면 Greedy, DP를 가장 먼저 의심해야 한다.
이 문제의 경우에는 미래에 대한 예측이 필요하므로, Greedy는 배제해야 할 것 같다.
예를 들어, 현재 길을 수정하지 않고 뒤의 길을 수정했을 때 경로가 만들어진다면?
우리는 Greedy하게 해당 값을 찾을 수 없으니, 배제하는 것이 맞다.

따라서 DP로 푸는 방법을 한 번 생각해보자.
DP는 이전 단계의 결과를 현재 단계에 이용하는 것이다.
그럼, 로그를 따라가면서 이전 시간의 결과를 현재 시간에 이용할 수 있을 것이다.
이전 시간에 수정을 한 횟수를 그대로 현재 시간으로 옮겨오는 것이다.

문제 적용

먼저 DP[x][y]의 2차원 배열을 선언하려고 한다.
여기서 x의 의미는 x번째 로그가 될 것이다.
또한 y가 의미하는 바는 현재 택시가 위치한 정점이 된다.
즉, x번째 로그에서 택시가 y에 위치하는 경우가 DP[x][y]인 것이다.

만약 DP[x][y]를 검사했을 때, 로그에 기록되었지만 갈 수 없는 경로라면?
다른 연결된 y 찾아 수정을 해주어야 할 것이다.

아래와 같이 for문을 통해서 DP 배열을 채워나갈 것이다.

dp[0][gps_log[0]] = 0; // 초기값, 택시의 처음 위치에서는 0
for (int i = 1; i < gps_log.size(); i++) {
    for (int j = 1; j <= n; j++) { 
        if (dp[i - 1][j] == INF)
            continue; // 이전 시간에 봤을 때, 경로가 없다? 패스
            
        for (int d = 0; d < graph[j].size(); d++) {
            int next_node = graph[j][d];
            int fix_cnt = 0;

            if (gps_log[i] != next_node)
                fix_cnt++; // 로그에 기록된 정점과 다르면 수정해야 함

            dp[i][next_node] = min(dp[i][next_node], dp[i - 1][j] + fix_cnt);
            // 이전 시간 경로 + 수정 횟수로 갱신한다.
        }
    }
}

가장 바깥의 for문은 GPS 로그를 도는 for문이다.
위에서 언급했듯이, 우리가 가장 관심을 가져야 할 부분은 로그이다.

그 안의 for문은 이전 시간 i - 1에 위치할 수 있었던 정점이다.
이전 시간 i - 1에 정점 j에 위치한 적이 있는가? 를 탐색한다.
그렇기에 if문을 통해서 위치한 적이 있는 정점인지를 판단한다.

그 안의 for문은 이전 시간에 위치했던 정점에 연결된 정점을 탐색한다.
즉, 현재 시간 i에 갈 수 있는 경로를 탐색하는 것이다.
만약 실제 로그에 기록된 i일 때 정점 j와 여기서 탐색한 정점이 다르다면?
그것은 수정할 필요가 있는 경로라는 의미로, 수정 횟수 + 1을 해주면 된다.

min() 함수를 통해, i 시간에 next_node로 갈 때의 수정 횟수를 갱신한다.
최소의 수정 횟수를 찾아야 하기 때문에, min()으로 갱신을 해야 한다.

최종적으로 아래의 값이 답이 된다.

if (dp[k - 1][gps_log[k - 1]] != INF)
        answer = dp[k - 1][gps_log[k - 1]];
    else
        answer = -1;

k번째 로그, 즉 마지막 위치가 INF가 값으로 갱신이 되었다면?
해당 값을 그대로 출력하고, 아니면 갈 수 없는 것이므로 -1을 출력한다.

상당히 어려운 DP 문제였다.
이런 문제도 스스로 생각해서 풀 수 있을 때 까지 열심히 해보자.