Programmers - GPS
title: Programmers - GPS
date: 2022-09-25
tags:
- Algorithm
- DP
https://school.programmers.co.kr/learn/courses/30/lessons/1837
문제 요약
그래프로 이루어진 거점을 이동하거나 머무를 수 있다.
시작점과 도착점은 고정이며, 주어진 경로의 거점을 변경할 수 있다.
주어진 경로를 수정하여 도착점까지 이동할 수 있을 때, 최소한으로 수정하는 횟수를, 도착이 불가능하면 -1을 return한다.
문제 풀이
거점은 200개, 경로의 최대 길이는 100으로 개수가 적다고 느낄 수 있으나 경로 수정의 알고리즘에 따라 TLE가 발생하기 쉬운 문제이다.
처음에는 앞에서부터 이동 가능한지 비교하며, 중간에 이동 불가능한 거점이 있을 경우 해당 거점을 수정하는 DFS 알고리즘을 작성하였다.
역시나 TLE가 발생하였고, 이 알고리즘이 잘못되었다는 것은 증명하기 쉽다.
간단하게 1-2-3-4-5의 매우 간단한 경로가 존재한다고 가정하자. GPS의 경로는 1-1-3-4-5-5가 주어졌다고 가정한다.
위 알고리즘이라면 3을 발견했을 때 문제가 발생하여 3부터 바꾸기 시작한다. 이렇게 수정한 경로는 1-1-2-3-4-5가 되며 3회가 최소 수정 횟수이다.
하지만 처음에 2로 넘어가는 1-2-3-4-5-5의 경우 한 번만 수정하면 된다.
결국 현재까지의 경로가 어떻든 모든 경로를 점검해야 하기에 DFS를 이용하면 O(n!)의 알고리즘이 유일하다.
이렇게 모든 위치를 점검할 때 DFS, BFS가 과한 시간복잡도가 나올 경우 경험상 DP를 사용하면 해결할 수 있었다.
vDP [ i ] 를 현재 i에 도착할 때 최소 수정 횟수라고 하면 된다.
다만 다음의 도착 정보를 업데이트할 때, 이전까지의 최소 수정 횟수에 대한 값들이 변경이 되어 과거와 현재의 값이 섞이는 문제가 발생한다.
그렇기에 이 배열을 2개로 만들어 한 DP 배열에는 업데이트를, 나머지 DP 배열에는 이전까지의 최소 수정 횟수를 저장한다.
각 단계에서 도착점을 기준으로 경로와 동일하면 iGap을 0, 아니라면 1로 설정하여 미리 현재 DP 배열을 갱신한다.
이후 모든 점에서 해당 도착점으로 바로 이동할 수 있다면(Edge 존재) 값을 비교하여 DP 배열을 갱신한다.
그냥 간단한 알고리즘 문제라고 볼 수 있으나, 실제로 GPS 정보가 실시간으로 들어오더라도 위치나 시간이 잘못 들어올 가능성이 존재한다.
유저들의 이동 경로 및 시간을 통해 현재 도로 상황 및 최적 길찾기를 제공할 경우, 이러한 정보들을 올바르게 바꾸는 것이 중요하다.
이 때 과연 이러한 DP 방식으로 정보들을 올바르게 수정할 수 있을까?
경로의 길이가 x, 거점의 개수가 n이라고 할 경우 위 알고리즘을 적용하면 O(n^2 * x)의 시간 복잡도가 나온다.
운전 시간이 길어질수록 경로의 길이도 길어질 것이며, 그만큼 거점의 개수는 기하급수적으로 늘어날 수 있다.
이러한 상황에서는 DP 방식을 적용하더라도, 이보다 훨씬 정교하고 빠르게 시행 가능한 알고리즘이 필요할 것이다.
프로그램
#include <vector>
#include <algorithm>
using std :: vector ;
using std :: min ;
int solution ( int n , int m , vector < vector < int > > edge_list , int k , vector < int > gps_log )
{
vector < vector < bool > > vPath ( n , vector < bool > ( n , false ) ) ;
vector < vector < int > > vDP ( 2 , vector < int > ( n , 1000 ) ) ; // [ 0 ] current, [ 1 ] former
int iEdgeSize = edge_list.size () ;
int iGpsSize = gps_log.size () ;
for ( int i = 0 ; i < iEdgeSize ; ++i )
{
int iFirst = edge_list [ i ] [ 0 ] - 1 ;
int iSecond = edge_list [ i ] [ 1 ] - 1 ;
vPath [ iFirst ] [ iSecond ] = true ;
vPath [ iSecond ] [ iFirst ] = true ;
}
for ( int i = 0 ; i < n ; ++i )
{
vPath [ i ] [ i ] = true ;
}
vDP [ 0 ] [ gps_log [ 0 ] - 1 ] = 0 ;
for ( int i = 1 ; i < iGpsSize ; ++i )
{
for ( int j = 0 ; j < n ; ++j ) // Copy i - 1 DP to former
{
vDP [ 1 ] [ j ] = vDP [ 0 ] [ j ] ;
}
for ( int iTarget = 0 ; iTarget < n ; ++ iTarget ) // Update DP
{
int iGap = ( iTarget == gps_log [ i ] - 1 ) ? 0 : 1 ;
vDP [ 0 ] [ iTarget ] += iGap ;
for ( int iStart = 0 ; iStart < n ; ++ iStart )
{
if ( ! vPath [ iStart ] [ iTarget ] ) // No path exist
continue ;
vDP [ 0 ] [ iTarget ] = min ( vDP [ 0 ] [ iTarget ] , vDP [ 1 ] [ iStart ] + iGap ) ;
}
}
}
if ( 1000 <= vDP [ 0 ] [ gps_log [ iGpsSize - 1 ] - 1 ] )
return -1 ;
return vDP [ 0 ] [ gps_log [ iGpsSize - 1 ] - 1 ] ;
}