프로그래머스 Lv3 GPS

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

프로그래머스

이 문제는,,,너무 어려웠다,,,

처음에는 다익스트라로 풀고, 처음부터 마지막 경로까지 가는데 막힌 부분이 있다면 로그를 확인해서 경로를 수정하는 방법으로 풀려고 했다.

하지만 위 풀이는 막히기 전에 경로를 수정할 때 해결을 하기가 어려웠다.

 

다른 사람들은 dp(dynamic programming)으로 풀었다.

현재 시간에 모든 거점에서 이전 시간의 모든 거점과 이전 시간의 거점에서 연결 된 거점들에서 수정한 부분을 메모제이션 해서 푼다는 방법으로 접근한다. 

 

DP의 핵심 아이디어는 다음과 같다.

• DP[시간][거점번호]
• DP 행 : 거점을 지나는 시간
• DP 열 : 현재 시간에 도착해 있는 거점 번호

---

문제 풀이

1. 거점과 거점 간 도로를 연결한다.

vector<vector<int> > connect(n+1,vector<int>());

for(int i = 0;i < edge_list.size();i++){
	connect[edge_list[i][0]].push_back(edge_list[i][1]);
	connect[edge_list[i][1]].push_back(edge_list[i][0]);
}

2. DP를 k행(시간) n + 1(거점)열로 만들고 INX_MAX - gps_log.size() 값으로 초기화한다.

vector<vector<int> > dp(k,vector<int>(n+1,INT_MAX - gps_log.size()));

• DP는 DP[시간][거점 번호] 의미를 가진다.
• DP는 이후에 (+1) 연산을 수행하는 데 오버플로(Overflow)를 방지하기 위해서 INT_MAX - gpos_log.size() 값으로 초기화 했다.

3. 시간이 0 일 때 위치는 자기 자신이므로 0으로 초기화했다.

dp[0][gps_log[0]] = 0;	//오류 수정 값(0)

4. GPS 정보 시간 (k, 시간대별로 보내오는 거점 정보의 총 개수) 만큼 반복

for(int i = 1;i < k;i++)

• 거점 개수(n) 만큼 반복

for(int j = 1;j <= n;j++)

1. (i)시간에 (j) 거점을 가려고 할 때 (i -1)시간에 (j)거점에 있었는지 확인, 최솟값 선택
2. 이 코드는 이해가 안갔다. (i -1)시간에 (j) 거점에 있으면 0을 더할 것이고, 없다면 INF_MAX - gpos_log.size() 값으로 나올텐데 궁금해서 이 부분을 삭제하고 코드를 돌려도 문제가 없었다.
3. 결국은 이전 시간에 연결 된 거점으로 경로를 수정해야만 답이 나오는 것이다!

dp[i][j] = min(dp[i][j],dp[i-1][j]+(gps_log[i] == j ? 0 : 1));

4. (i)시간에 (j)거점을 가려고 할 때 (i-1)시간에 (j)거점과 연결되어 있는 (connect[j][l])까지 확인하여 현재 거점과 연결하려고 시도한다. 이렇게하면 j값은 달라질 수 밖에 없기에 gps_log[i] == j ? 0 : 1은 1이 나올 수밖에 없다.

거점들은 서로 연결되기에 이렇게 푸는 것이 가능하다.

DP[1][2] = min(DP[1][2], DP[0][connect[2][l]] + (gps_log[1] == j ? 0 : 1))

(i = 1, j = 2) 일 때 2번에 연결 된 거점은 1번이므로 값이 갱신된다.

(i = 1, j = 3) 일 때 3번에 연결 된 거점은 2번이므로 값이 갱신된다.

            for(int l = 0; l < connect[j].size(); ++l)
            {
                DP[i][j] = min(DP[i][j], DP[i - 1][connect[j][l]] + (gps_log[i] == j ? 0 : 1));
            }

5. DP[GPS 마지막 시간][GPS 도착 거점] 이 초기값 (INT_MAX - gps_log.size())인지 확인

• 초기값이면 수정 불가(-1), 아니면 경로를 최소로 수정 한 값(DP[k-1][gpos_log.back()])

#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) 
{
    int answer = 0;
    vector<vector<int>> connect = vector<vector<int>>(n + 1, vector<int>());
    
    for(int i = 0; i < edge_list.size(); ++i)
    {
        connect[edge_list[i][0]].push_back(edge_list[i][1]);
        connect[edge_list[i][1]].push_back(edge_list[i][0]);
    }
    
    vector<vector<int>> DP = vector<vector<int>>(k, vector<int>(n + 1, INT_MAX - gps_log.size()));
    
    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] + (gps_log[i] == j ? 0 : 1));
            
            for(int l = 0; l < connect[j].size(); ++l)
            {
                DP[i][j] = min(DP[i][j], DP[i - 1][connect[j][l]] + (gps_log[i] == j ? 0 : 1));
            }
        }   
    }
    
    return DP[k - 1][gps_log.back()] == INT_MAX - gps_log.size() ? -1 :  DP[k - 1][gps_log.back()];
}