프로그래머스 - GPS

프로그래머스 - GPS

DP로 풀어야하는 문제로 점화식은 다음과 같다.

DP[i][j] = i번째 경로가 j일 때, 수정해야하는 경로의 최소 횟수

i번째에 경로가 j가 된다는 것은, i-1번째에 j에 머물고 있거나 혹은 j와 인접한 노드에 있었다는 의미이다.
먼저 주어진 edge_list를 이용해서 graph를 만들고, dp[0]gps_log[0]]을 0으로 설정하고 나머지는 충분히 큰 숫자로 설정한다.
그 후 다음 점화식을 따른다.

1. i - 1번째에 j번째에 머물었는지 체크

dp[i][j] = MIN(dp[i][j], dp[i - 1][j])

2. i - 1번째에 j와 인접한 노드로부터 올 수 있는지 체크

for(auto it : graph[j])
	dp[i][j] = MIN(dp[i][j], dp[i - 1][it])

3. gps_log[i]번째와 숫자가 일치하는지 체크
   dp[i][j] += (gps\_log[i] == j) ? 0 : 1;

코드는 아래와 같다.

#include <vector>

using namespace std;

#define MIN(a, b) ((a < b) ? a : b)
#define MAX_LIMIT 1e7

int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    int answer = 0;
    
    vector<vector<int>> dp(k, vector<int>(n + 1, MAX_LIMIT));
    vector<vector<int>> graph(n + 1);

    for(int i=0;i<m;i++) {
        graph[edge_list[i][0]].push_back(edge_list[i][1]);
        graph[edge_list[i][1]].push_back(edge_list[i][0]);
    }
    
    dp[0][gps_log[0]] = 0;
    for(int i = 1; i < k; i++) {
        for(int j = 1; j <= n; j++) {
            dp[i][j] = MIN(dp[i][j], dp[i - 1][j]);
            for(auto it : graph[j]) 
                dp[i][j] = MIN(dp[i][j], dp[i - 1][it]);
            dp[i][j] += (j == gps_log[i]) ? 0 : 1;
        }
    }
    
    answer = dp[k - 1][gps_log[k - 1]] >= MAX_LIMIT ? -1 : dp[k - 1][gps_log[k - 1]];
    
    return answer;
}