공부하는 식빵맘 👱‍♀️

공부하는 식빵맘 👱‍♀️

반갑습니다 :)

[C++로 풀이] GPS (DP)⭐⭐⭐

Date:     Updated:

카테고리:

태그:

📌 GPS

난이도 ⭐⭐⭐

🚀 문제

image

image

image

image

image


🚀 내 풀이 ⭕

이 문제는.. 한 1시간 고민하다가 전혀 모르겠어요^_^ 하고는 다른 분들의 풀이를 보고 이해해서 겨우 푼 문제다. DP 문제에 너무 약한 것 같다.. DP 문제라고 감도 못 잡았는데 ㅠ ㅠ.. 큰 일이다. DP 문제 많이 풀어봐야겠다 싶다..!!🔥🔥

#include <vector>
#include <algorithm>

using namespace std;

#define INF 987654321

int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log){
    int answer = 0;
    // road 는 인접 리스트
    // 인덱스는 각 지점에 대응. 지점마다 자신과 인접한 지점들을 추가 
    // ex) road[2] = [3, 4]  2 지점은 3, 4 지점과 연결된 상태임을 의미함.
    vector<vector<int>> road(n + 1); 
    for (int i = 0; i < edge_list.size(); ++i) {
        road[edge_list[i][0]].push_back(edge_list[i][1]);
        road[edge_list[i][1]].push_back(edge_list[i][0]);
    }

    // dp의 모든 원소를 INF 로 초기화 해야함
    vector<vector<int>> dp(k, vector<int>(n + 1, INF)); 
    dp[0][gps_log[0]] = 0; // 시작점 고정 (0 초의 시작점의 최소 수정횟수는 0)
    for (int t = 1; t < k; ++t) { // t = 0 은 위에서 구했으니 제외 (t = 0 땐 무조건 시작점에서 시작해야 함. 이 경우만 고려 되야 함)
        for (int pos = 1; pos <= n; ++pos) {
            
            /* 아래 경우들에서 가장 최소 수정 횟수를 가지는 경우를 그대로 물려 받는다. */
            // 1초전에도 pos에 있었던 경우(그대로 머무른 경우) 
            int minValue = dp[t - 1][pos]; 
            // pos 와 인접한 지점들에서 온 경우 
            for (int i = 0; i < road[pos].size(); ++i)
                minValue = min(dp[t - 1][road[pos][i]], minValue);
            
            if (gps_log[t] != pos) 
                dp[t][pos] = minValue + 1; // 수정이 필요하다면 +1 
            else 
                dp[t][pos] = minValue; // 아니라면 냅둠
        }
    }

    answer = dp[k - 1][gps_log[k - 1]]; // gps_log[k-1] 즉, 마지막 시간대인 k-1 초에 목적지까지 필요한 최소 수정 횟수
    if (answer >= INF) answer = -1;  // dp[k - 1][gps_log[k - 1]] 가 INF 보다 크다는 것은 수정이 불가능한 경우
    return answer;
}
  • DP 로 해결하는 하는 이유
    • 앞 부분 로그의 오류를 하나 고쳤다면 그 순간부터 경로 자체가 바뀌는 것이나 마찬가지이기 때문에(edge_list말고 gps_log의 경로) 그 뒤의 로그들의 수정 여부에도 전부 영향을 끼치게 된다. 앞 로그 중 어느 한 곳을 올바르게 수정하면 뒤의 로그 중에서도 이의 영향으로 수정 안해도 되게끔 된다던지..! 하는 그런 영향이 뒤의 로그들에게 전부 미치게 된다.
    • 입력 크기가 큰지라 완전탐색을 한다면 시간 초과가 발생할게 분명하다.
    • t시간까지 오는데까지 pos 지점의 최소 수정 횟수를 구해놓는다면, 그 이후의 시간의 인접 노드 지점의 최소 수정 횟수를 구하는데 쓰이게 된다.
      • 즉, 부분적인 최적해로 전체적인 최적해를 찾아가는 방식인 것이다.
      • 수정할 사항이 없으면 인접한 지점들 중 가장 최소로 수정한 횟수를 물려받으면 되는 것이다.
  • t시간엔 gps_log[t] 거점에 있었다는 로그 정보가 있으니, 현재 edge_list에서 그 정보대로 따르는게 불가능하다면 수정 횟수를 1 증가시켜 수정해주어야 한다.

dp[t][pos] = t시간까지(즉, t번째나 마찬가지) pos 지점으로 오는데까지 최소로 수정한 횟수 (t의 범위는 0~k-1. 문제에선 1~k 로 설명 됐지만 0~k-1로 쓰는게 gps_log의 인덱스와도 일치하니 편해서 0~k-1로 쓰겠다.)

  • dp 테이블의 크기는 (k) x (n + 1) 이 된다. (n + 1)인 이유는 거점 이름과 인덱스를 일치시키기 위하여!
  • dp[0][gps_log[0]] : 0 초까지의 시작 지점으로 오는데까지 최소로 수정한 횟수
    • dp[0][gps_log[0]] = 0
      • 시작 거점과 도착 거점은 고정적이라고 문제에서 제한했다.
        • 도착 거점이야 그냥 dp[k-1][gps_log[k-1]] 을 리턴하면 되는데, 시작 거점은 DP 의 시작이니 확실히 고정되어야 한다.
      • 시작 거점이니 당연히 최소 수정횟수는 0 !
  • dp[t][pos] : t 초까지의(=t번째) pos 지점으로 오는데까지 최소로 수정한 횟수
    • dp[t][pos] = min(그대로 머물렀을 때의 최소 수정 횟수, 연결된 모든 정점들에서 왔을 때의 최소 수정 횟수) + (수정이 필요한 경우엔 +1)
      • 1️⃣ 아래 중 더 작은 값을 가지는 것을 선택하여 대입 받는다. (그 최소 수정 횟수를 그대로 물려받는다.)
        • dp[t - 1][pos]
          • 1초 전에도 pos에 있었을 때, 즉 그대로 머물렀을 때의 최소 수정 횟수
          • 즉, t-1 초까지 pos 지점으로 오는데까지 최소로 수정한 횟수 
            int minValue = dp[t - 1][pos];
        • dp[t - 1][road[pos][i]]
          • road[pos][i] 는 pos 지점과 연결된 지점이다. road 인접리스트로 알아낼 수 있다.
          • for문을 순회하며 pos와 연결된 
            for (int i = 0; i < road[pos].size(); ++i)
  minValue = min(dp[t - 1][road[pos][i]], minValue);
        • 이렇게 최종적으로 pos에 그대로 머물렀을 때, 각각 pos와 연결된 지점들에서 왔을 때, 이렇게 모든 후보들 중에서 가장 작은 값의 수정 횟수를 가지는 경우를 그대로 물려 받는다. 
          dp[t][pos] = minValue;
      • 2️⃣ 수정이 필요하다면 1을 더해준다. (1회 수정)
        • 현재 dp[t][pos] 즉, t 초까지 pos 지점으로 오는데까지 최소로 수정한 횟수를 구한 것인데 실제 로그 정보에서 t 초에는 pos가 아닌 다른 지점에 있었다면 t초에 pos 지점으로 오려면 수정이 필요하다는 뜻이다.
        • 따라서 gps_log[t](로그 상에서 t초에 간 지점)이 pos와 일치하지 않으면 1을 추가로 더해준다.
        • 수정 필요하지 않으면 이 과정은 그냥 넘어가면 됨.
        • DP이다 보니 이렇게 모든 경우를 다 저장해두는 것이다. 
          if (gps_log[t] != pos) 
    dp[t][pos]++;

#include <vector>
#include <algorithm>

using namespace std;

#define INF 987654321

int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log){
    int answer = 0;
    vector<vector<int>> road(n + 1);
    for (int i = 0; i < edge_list.size(); ++i) {
        road[edge_list[i][0]].push_back(edge_list[i][1]);
        road[edge_list[i][1]].push_back(edge_list[i][0]);
    }

    vector<vector<int>> dp(k + 1, vector<int>(n + 1, INF));
    dp[1][gps_log[0]] = 0;
    for (int t = 2; t <= k; ++t) {
        for (int pos = 1; pos <= n; ++pos) {
            int minValue = dp[t - 1][pos];
            for (int i = 0; i < road[pos].size(); ++i)
                minValue = min(dp[t - 1][road[pos][i]], minValue);
            if (gps_log[t - 1] != pos) dp[t][pos] = minValue + 1;
            else dp[t][pos] = minValue;
        }
    }

    answer = dp[k][gps_log[k - 1]];
    if (answer >= INF) answer = -1;
    return answer;
}

이 풀이는 문제에서 주어진대로, t의 범위를 1 ~ k로 놓았을 때의 풀이.


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)