[ 프로그래머스 GPS (Lv3) ] (C++)

프로그래머스의 GPS(Lv3) 문제이다.

[ 문제풀이 ]

수식을 하나 이용해서 문제에 접근해보자.

F[A][B] = C 라는 수식을 사용할 것인데, 이 수식의 의미는 다음과 같다.

F[A][B] = C : "A번 지점이 B가 되었을 때, 경로를 수정해야 하는 최소 횟수는 C회입니다."

여기서 "A번 지점" 이라는 것은 "A번째 경로" 를 의미한다.

그럼 초기값으로 다음과 같은 식을 설정해 줄 수 있다.

F[0][gps_log[0]] = 0.

위의 식에서 gps_log[0] 는 택시가 가장 처음에 머물렀던 지점을 의미한다.

즉, 위의 식을 풀어서 이야기해보면, "0번째 지점을, 택시가 가장 처음에 머물렀던 지점으로 설정하게 되면, 경로를 수정해야 하는 최소 횟수는 0회입니다." 를 의미한다.

택시는 0번째 지점, 즉, 가장 처음에는 당연히 "택시가 가장 처음에 있었던 지점"에 있어야 한다.

그리고 이 경우에 그 어떠한 경로를 수정하지 않아도 되기 때문에 수정한 횟수는 0회가 된다.

따라서 위와 같은 초기값을 설정해 줄 수 있다.

그리고 이제 모든 지점에 대해서 탐색을 한번 해보자.

만약 현재 택시가 "A번째 경로를 B번 지점으로 설정하기 위한 상황" 을 생각해보자.

A번째 경로를 B번 지점으로 설정하기 위해서는 먼저 1가지 조건이 필요하다.

바로, "A - 1번째로 설정된 지점과 B번 지점이 연결되어 있어야 한다" 는 것이다.

연결되어 있지 않다면, 경로를 수정할 수 없기 때문이다.

이 판단은 우리가 위에서 설정해 놓은 수식으로 할 수 있다.

탐색 과정에서 "A번째 경로를 선택하는 과정" 이라면, 이전에 이미 "A - 1번째 경로를 선택하는 과정"이 계산이 되어 있을 것이고, 만약, F[A - 1][B]의 값이 계산이 되지 않는 값이라면, 즉, "수정할 수 없다는 것을 의미" 하고 있다면, 이는 연결이 되지 않았다고 판단할 수 있다.

만약, 연결되어 있는 경로라면, 수정한 횟수를 계산하면 된다.

만약, 기존에 주어진 A번째 경로에 머문 지점이 B라면, 수정을 하지 않아도 되겠지만, 그게 아니라면 수정한 횟수를 +1회 시켜주면 된다.

[ 소스코드 ]

#include <vector>
 
#define MAX 210
#define INF 2e9
using namespace std;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) 
{
    vector<int> Node[MAX];
    vector<vector<int>> DP(k, vector<int>(n + 1, INF));
    for (int i = 0; i < edge_list.size(); i++)
    {
        int N1 = edge_list[i][0];
        int N2 = edge_list[i][1];
        Node[N1].push_back(N2);
        Node[N2].push_back(N1);
    }
 
    // DP[A][B] = C : 경로의 A번 지점이 B가 되었을 때, 수정해야 하는 횟수
    // 초기값 = DP[0][gps_log[0]] = 0
    DP[0][gps_log[0]] = 0;
    for (int i = 1; i < k; i++)
    {
        for (int Cur = 1; Cur <= n; Cur++)
        {
            if (DP[i - 1][Cur] == INF) continue;
            
            for (int j = 0; j < Node[Cur].size(); j++)
            {
                int Next = Node[Cur][j];
                int Alpha = 0;
                if (gps_log[i] != Next) Alpha++;
                
                DP[i][Next] = Min(DP[i][Next], DP[i - 1][Cur] + Alpha);
            }
        }
    }
 
    if (DP[k - 1][gps_log[k - 1]] < INF) return DP[k - 1][gps_log[k - 1]];
    return -1;
}