하루 하루는 성실하게
인생 전체는 되는대로

[프로그래머스] GPS

1 minute read

문제 설명

카카오 택시 개발자 Jay-G는 다음 업데이트를 준비하기 위해 개선사항을 위한 여러 피드백을 받았다. 그중에서 손님이 자주 탑승하는 위치를 추천해주었으면 한다는 의견이 많았다.

다음 업데이트 준비를 위해 Jay-G는 택시의 승하차 및 이동 경로를 수집하여 분석하기 시작하였다. 데이터를 분석하던 Jay-G는 몇 가지 특이사항을 발견했다. 택시의 이동 경로를 GPS를 통해 수집하게 되는데, GPS 신호 불량, 통신 오류 등 다양한 원인으로 위치의 오류가 발생한 것을 알게 되었다. 다만 승차 위치와 하차 위치는 오류가 없는 것으로 확인이 되었다.

개발자 Jay-G는 수집한 이동 경로의 오류를 최소한으로 수정하여 좀 더 정확한 이동 경로를 구하고 싶어 한다.

택시는 다음과 같은 조건으로만 이동한다. 먼저 택시는 거점을 이동해 다니며, 거점 간의 이동은 해당하는 도로가 있는 경우에만 가능하다. 또한, 교통 상황에 따라 택시는 한 거점에 머무를 수 있고, 왔던 길을 되돌아갈 수 있다. 모든 도로는 방향이 별도로 없는 왕복 도로이다.

/* 중략 */

위와 같이 택시가 보내온 경로에서 이동 가능한 경로로 만드는 최소의 오류 수정 횟수를 구하여라.

제한사항

  • 2 <= n <= 200
  • 1 <= m <= 10,000
  • 2 <= k <= 100
  • edge_list는 m × 2 크기의 2차원 배열로, 각 행의 두 값은 도로가 잇는 두 거점의 번호를 의미한다.
  • 거점의 번호는 1부터 n까지 숫자이다.
  • 모든 도로는 양방향 통행이 가능하다.
  • 입력되는 데이터에서 항상 모든 거점 간 경로가 있음이 보장되지 않는다.
  • gps_log의 시작 거점과 도착 거점은 바뀔 수 없다.

풀이

실패
k의 범위가 100보다 작으므로 가지치기를 잘 하면 DFS로 풀이할 수 있을거라 생각했지만, 시간 초과로 실패했다. 이후 DP 풀이법을 계속 고민했는데, 결국 해결하지 못하고 다른 사람의 풀이를 참고하게 되었다.

dp[i][j] => // i번째 gps로그값이 j일 때, 최소 수정 횟수

위의 힌트를 얻고도 잘 이해되지 않아서 한동안 고민했었는데, 문제를 풀기 위해 직접 손으로 그려보니 위의 식이 이해가 되었다.

코드

#include <vector>
#include <algorithm>

using namespace std;


int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    
    vector<vector<int>> dp(k , vector<int>(n+1, 10000));
    vector<int> adj[201];
    
    dp[0][gps_log[0]] = 0;
    
    for(vector<int> v : edge_list){
        adj[v[0]].push_back(v[1]);
        adj[v[1]].push_back(v[0]);
    }
    
    for(int i = 1; i < gps_log.size(); ++i){
        for(int j = 1; j <= n; ++j){
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
            for(int k : adj[j]){
                dp[i][j] = min(dp[i][j], dp[i - 1][k]);
            }
            if(j != gps_log[i]) dp[i][j] += 1;
        }
    }
    
    if(dp[k - 1][gps_log[k-1]] >= 10000) return - 1;
    return dp[k - 1][gps_log[k-1]];
}

참고문헌

https://softworking.tistory.com/417

You may also enjoy