GPS - level 4

해결방법

먼저 점화식을 세워보자!
$$ dp[i][j] = min(dp[i][j], dp[i-1][here] + error) $$
여기서 i는 시간을 의미하고, j는 각 노드를 의미한다. here은 j노드와 연결된 인접노드를 의미한다. dp[i][j]는 이전 시간 인접노드들의 에러들 중 최소를 + error(1 또는 0)을 의미한다.

int dp[110][210]; // 시간과 노드로 구성된 dp
int error = gps_log[i] == j ? 0 : 1; // gps_log[i]와 현재 노드가 같다면 0 아니면 1

초기화 과정이다. adj[i].clear()는 꼭 써주자! 아무래도 프로그래머스는 전역변수도 초기화가 안되는 모양이다.

for(int i=0;i<210;i++) adj[i].clear();
    for(int i = 0; i < 110; ++i)
        for(int j = 0; j < 210; ++j)
            dp[i][j] = INF;
    for(int i = 0; i < edge_list.size(); ++i) {
        int s = edge_list[i][0];
        int e = edge_list[i][1];
        adj[s].push_back(e);
        adj[e].push_back(s);
    }

항상 처음과 마지막은 옳기 때문에 dp[0][처음 gps위치] = 0으로 초기화 시켜준다. 이후에는 i시간 때 모든 노드를 조사하여 몇 번까지 error가 몇 번인지 구하면 된다.

dp[0][gps_log[0]] = 0;
    for(int i = 1; i < k; ++i) {
        for(int j = 1; j <= n; ++j) {
            int error = gps_log[i] == j ? 0 : 1;
            dp[i][j] = min(dp[i][j], dp[i-1][j] + error);
            for(auto here : adj[j])
                dp[i][j] = min(dp[i][j], dp[i-1][here] + error);
        }
    }
answer = dp[k-1][gps_log.back()];

전체코드

#include <vector>
#include <iostream>
using namespace std;
vector<int> adj[210];
int dp[110][210];
const int INF = 987654321;
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    int answer = INF;
    for(int i=0;i<210;i++) adj[i].clear();
    for(int i = 0; i < 110; ++i)
        for(int j = 0; j < 210; ++j)
            dp[i][j] = INF;
    for(int i = 0; i < edge_list.size(); ++i) {
        int s = edge_list[i][0];
        int e = edge_list[i][1];
        adj[s].push_back(e);
        adj[e].push_back(s);
    }
    dp[0][gps_log[0]] = 0;
    for(int i = 1; i < k; ++i) {
        for(int j = 1; j <= n; ++j) {
            int error = gps_log[i] == j ? 0 : 1;
            dp[i][j] = min(dp[i][j], dp[i-1][j] + error);
            for(auto here : adj[j])
                dp[i][j] = min(dp[i][j], dp[i-1][here] + error);
        }
    }
    answer = dp[k-1][gps_log.back()];
    if(answer >= INF) answer = -1;
    return answer;
}