프로그래머스 GPS

코드

#include <vector>
#include <algorithm>
#include <iostream>
#define INF 1e9
using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    int answer = 0;
    vector<int> graph[201];
    
    for (auto i : edge_list) {
        graph[i[0]].push_back(i[1]);
        graph[i[1]].push_back(i[0]);
    }
    for(int i=1;i<=n;i++) graph[i].push_back(i);
    vector<vector<int>> dp(k, vector<int>(n + 1, INF));

    dp[0][gps_log[0]] = 0;
    for (int i = 0; i < k - 1; i++) {
        for (int j = 1; j <= n; j++) {
            if (dp[i][j] == INF) continue;

            for (int k : graph[j]) {
                int re = dp[i][j];
                if (gps_log[i + 1] != k) re++;

                dp[i + 1][k] = min(dp[i + 1][k], re);
            }
        }
    }
    answer = dp[k - 1][gps_log[k - 1]];
    if(answer==INF) return -1;
    
    return answer;
}

풀이

먼저 인접리스트 방식으로 그래프를 구현해줬습니다

    vector<int> graph[201];

    for (auto i : edge_list) {
        graph[i[0]].push_back(i[1]);
        graph[i[1]].push_back(i[0]);
    }
    for(int i=1;i<=n;i++) graph[i].push_back(i);

문제에서 노드는 그 자리에 머무를 수도 있기 때문에 리스트에 자기 자신의 노드도 포함시켜주는 것이 뽀인트입니다.

dp테이블을 만들고 무한으로 초기화 시켜줬습니다 dp에는 오류회수가 저장 되는데 처음 시작점은 0으로 초기화 해줍니다

dp테이블을 돌면서 값을 갱신해주는데 현재 값이 INF라면 넘깁니다 무한이 아니라면 현재 노드와 연결된 곳들을 다 체크하면서 만약 gps_log의 현재 시간과 같은 값이라면 오류값을 추가하지 않고 그대로 가져오고 다르다면 +1을 해주면서 채워주면 됩니다.