[프로그래머스]2017 카카오코드 본선 : GPS (level 3) (c++)

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

코딩테스트 연습 - GPS

 

DP

#include <vector>
#include <algorithm>

using namespace std;

const int INF = 987654321;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {

    // 인접 리스트 생성
    vector<vector<int>> adj_list(n + 1, vector<int>());
    for (int i = 0; i < m ; ++i)
    {
        int from = edge_list[i][0];
        int to = edge_list[i][1];

        adj_list[from].push_back(to);
        adj_list[to].push_back(from);
    }

    // D[i][j] : i번째 로그가 j일 때, i번째 j로 오기까지 고쳐야 하는 로그의 최소 횟수
    vector<vector<int>> D(k, vector<int>(n + 1, INF));
    
    // 시작경로와 끝 경로는 고정되어 있다.
    D[0][gps_log[0]] = 0;


    // gps_log의 2번째 자리부터 탐색
    for (int i = 1; i < k; ++i)
    {
        // gps_log의 i번째 자리가 j일때, 최소의 고친 횟수를 i - 1번째 값에서부터 가져오기
        for (int j = 1; j <= n; ++j)
        {
            // 이동하지 않고 다음턴에도 그자리에 가만히 있는 경우
            D[i][j] = min(D[i - 1][j], D[i][j]);

            // j에 연결된 인접 노드에서 j로 이동한 경우
            for (int adj : adj_list[j])
            {
                D[i][j] = min(D[i - 1][adj], D[i][j]);
            }

            // 로그를 고쳤다면 횟수 더해주기
            D[i][j] += (gps_log[i] == j) ? 0 : 1;
        }
    }


    // 올바른 경로로 수정하는 것이 불가능한 경우
    if (D[k - 1][gps_log[k - 1]] >= INF)
    {
        return -1;
    }

    // 끝 경로로 오기까지 고쳐야 하는 로그의 최소 횟수
    return D[k - 1][gps_log[k - 1]];
}

 

 

간선리스트와 (틀린)이동로그가 주어지고,

주어진 시작점~끝점까지 로그를 최소로 고친 횟수를 반환하는 문제였다.

 

시작점/끝점은 고정되어 있지만 중간에 있는 로그들은 어딘가 조금씩 틀려있다.

이 로그들을 고친다고 하면, 다음 로그는 앞서 고쳐진 로그의 영향을 받게된다.

입력되는 데이터에서 항상 모든 거점 간 경로가 있음이 보장되지 않는다.

문제에서 모든 노드가 연결되어 있지 않다고 했기 때문이다.

 

 

그래서 DP로 풀이해야 한다.

몇번째 어떤 노드를 고쳤는지, 그리고 그때의 최소 횟수는 어떤지를 메모이제이션 해야 한다.

즉, DP[i][j] : i번째 j노드로 오면서 최소로 고친 횟수

이렇게 2차원 배열로 메모이제이션 한다.

DP[i][j]는 DP[i - 1][j로 올수 있는 노드]의 최소값을 가져오고, 그 후에 현재 위치를 고친 횟수를 더해주게 된다.

 

 

j로 올수 있는 노드는 2가지 경우가 있다. 

택시는 거점을 이동해 다니며, 거점 간의 이동은 해당하는 도로가 있는 경우에만 가능하다.
또한, 교통 상황에 따라 택시는 한 거점에 머무를 수 있고, 왔던 길을 되돌아갈 수 있다. 

택시가 이동도 할 수 있지만, 그 자리에 머물러 있는 경우도 고려해주어야 한다. 

 

따라서 점화식은 다음과 같다.

DP[i][j] = min(DP[i - 1][인접 노드들], DP[i - 1][j]) + (log[i] == j ? 0 : 1)

 

 

 

 

풀이를 참고한 블로그

카카오 Code Festival 본선 1~6번 풀이

 

카카오 코드 페스티벌 2017 본선 해설(Ongoing)