프로그래머스 문제 - GPS

프로그래머스 GPS 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

각 노드 사이를 움직이는 택시의 이동 경로가 주어집니다.
주어진 이동 경로는 다양한 원인으로 위치에 오류가 발생하여 틀린 위치를 줄 수도 있습니다.
승차 위치와 하차 위치는 오류가 없으며 오류가 발생하지 않을 수도 있습니다.
또한, 교통 상황에 따라 택시는 한 거점에 머무를 수 있고, 왔던 길을 되돌아갈 수 있으며 모든 도로는 방향이 별도로 없는 왕복 도로입니다.
택시가 보내온 경로에서 이동 가능한 경로로 만드는 최소의 오류 수정 횟수를 구해야합니다.

문제 풀이

주어진 경로가 이동이 불가능한 경로인 경우 수정하여 이동 가능한 경로로 바꿔주는 최소 횟수를 구하는 문제입니다.

틀린 경로를 바꾸더라도 경로가 잘 이어지는지 확인이 지속적으로 필요하기 때문에 완전탐색으로 구현이 가능할 것입니다.
그러나 노드200개, 이동거리100개가 주어지므로 DFS는 시간초과가 날 것이니 DP를 사용하여 문제를 해결하는 것이 좋아보입니다.

일단 그래프이기 때문에 배열을 사용하여 노드와 간선들을 연결해줍니다.
이때 간선은 왕복 도로이며 움직이지 않고 한 거점에 머무를 수 있습니다.

//간선 등록
for(vector<int> v : edge_list)
{
    road[v[0]].push_back(v[1]);
    road[v[1]].push_back(v[0]);
}
//시작점은 언제나 0이고 택시가 머무를 수 있으므로 간선에 자기 자신 등록
for(int i = 1; i <= n; i++)
{
    road[i].push_back(i);
}

그리고 DP배열을 만들기 위해 몇차원 배열에서 어떤 값을 저장 및 재사용할지 정해야합니다.
현재 구하고 있는 값은 이동 가능한 경로로 만드는 오류 수정 횟수의 최소값이므로 이 값을 저장해줍니다
그리고 시간대별로 이동할 수 있는 정보가 담긴 배열과, 이동이 가능한 거점인 노드가 있습니다
이 정보들을 가지고 2차원 DP배열을 만들어줍니다.

dp[0][gps_log[0]] = 0;
for(int i = 1; i < k; i++)
{
    int cur = gps_log[i];   //현재 거점
    for(int j = 1; j <= n; j++)
    {
        int prevValue = dp[i-1][j]; //전 거점의 값
        if(prevValue == INF)
            continue;

        for(int nextRoad : road[j]) //전 거점으로부터 움직일 수 있는 거점
        {
            if(cur == nextRoad) //만약 움직일 수 있는 거점이 현재 거점하고 같을 경우
                dp[i][nextRoad] = min(dp[i][nextRoad], prevValue);  //경우의 수 최소값 등록
            else
                dp[i][nextRoad] = min(dp[i][nextRoad], prevValue+1);    //거점에 가지 못할 경우 경로 변경을 했다고 가정하여 +1을 해준 후 최소값 등록
        }
    }
}

택시의 승차 위치는 오류가 발생하지 않으므로 시작값은 승차 위치 노드값을 0으로 저장해줍니다.
그리고 현재 거점으로부터 바로 이전 거점들을 비교하며 계산해줍니다
이전 거점에서 현재 거점까지 올 수 없을 경우 이전 거점까지의 오류 수정횟수에 +1해서 값을 저장해주면 됩니다.
즉, 현재 거점까지의 오류 수정횟수 = min(현재 거점까지의 오류 수정횟수, 전 거점까지의 오류 수정횟수)입니다.

이후 DP배열 완성 후에는 마지막 거점 값을 return해주면 되고, 만약 불가능한 수가 나왔을 경우 -1을 return해줍니다.

전체 코드

#include <bits/stdc++.h>
#include <vector>

using namespace std;

#define INF 100000

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    int answer = 0;
    //시간과 노드들의 수로 만들어진 DP배열
    vector<vector<int>> dp(k, vector<int>(n+1, INF));
    vector<int> road[n+1];
    
    //간선 등록
    for(vector<int> v : edge_list)
    {
        road[v[0]].push_back(v[1]);
        road[v[1]].push_back(v[0]);
    }
    //시작점은 언제나 0이고 택시가 머무를 수 있으므로 간선에 자기 자신 등록
    for(int i = 1; i <= n; i++)
    {
        road[i].push_back(i);
    }
    dp[0][gps_log[0]] = 0;
    for(int i = 1; i < k; i++)
    {
        int cur = gps_log[i];   //현재 거점
        for(int j = 1; j <= n; j++)
        {
            int prevValue = dp[i-1][j]; //전 거점의 값
            if(prevValue == INF)
                continue;

            for(int nextRoad : road[j]) //전 거점으로부터 움직일 수 있는 거점
            {
                if(cur == nextRoad) //만약 움직일 수 있는 거점이 현재 거점하고 같을 경우
                    dp[i][nextRoad] = min(dp[i][nextRoad], prevValue);  //경우의 수 최소값 등록
                else
                    dp[i][nextRoad] = min(dp[i][nextRoad], prevValue+1);    //거점에 가지 못할 경우 경로 변경을 했다고 가정하여 +1을 해준 후 최소값 등록
            }
        }
    }
    //gps의 마지막 값의 dp값을 return
    if(dp[k-1][gps_log[k-1]] == INF)
        answer = -1;
    else
        answer = dp[k-1][gps_log[k-1]];
    
    return answer;
}

출저

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