[프로그래머스 Lv3] : GPS

문제 링크

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

프로그래머스

다양한 원인으로 인해 오류가 발생할 수 있는 GPS로 파악한 지나온 거점의 정보가 주어졌을 때,

최소한의 경로만 수정해서 가능한 경로가 되도록 만들어보자.

 

풀이

• 내가 떠올린 아이디어

일단 노드와 간선에 대한 정보가 주어졌기 때문에 나는 당연히 그래프 탐색을 이용해야한다고 생각했다.

나는 DFS를 이용해서 깊이가 k인 경로를 파악한 다음, 탐색한 경로와 주어진 GPS 경로가 같아지려면 몇 개의 정보를 수정해야하는 지 헤아렸다.

이때 수정해야하는 수가 가장 적은 것을 정답으로 처리하려했다.

이 방법이 틀린 방법은 아니다. 주어진 테스트케이스는 모두 통과했지만, 주어지는 노드와 간선의 수가 많아질 수록 경우의 수가 많아져서 시간초과가 발생했다.

 

여기서 더 나아가지 못하고 한 시간 정도를 고민하다가 결국 구글의 힘을 빌렸다.

3단계 문제가 맞나 싶을 정도로 어려운 문제였다. 지금까지 풀어본 바로 카카오 문제가 대체로 수준이 높은 듯하다.

 

참고한 링크

https://ansohxxn.github.io/programmers/130/

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

공부하는 식빵맘님의 풀이를 참고해서 풀었다. 설명을 너무 잘해놓으셔서 쉽게 이해할 수 있었다.

 

• 풀이 알고리즘

정답은 DFS, BFS 둘다 아닌 DP였다. 나는 DP를 쓸거라곤 생각도 못했는데 풀이를 보니 이해가됐다.

DP[시간][위치] 로 배열을 만들어서, 해당 시간에 해당 위치까지 오기위해 수정한 최소 횟수를 저장한다.

최종적으로 DP[K][마지막 정점] 에 저장되어있는 값이 정답이 될 것이다.

 

DP[ t ][ pos ] 값을 정하는 방법은 다음과 같다.

1. t - 1 초에도 pos 위치, 즉 같은 위치에 있었던 경우

2. t - 1 초에 인접한 위치에서 pos로 온 경우

두 경우 중에 수정횟수가 최소가 되는 값을 찾는다. 이때의 값을 Min이라고 하자.

pos가 GPS에 찍힌 t초일 때의 위치와 일치한다면 수정이 필요없으므로

DP[ t ][ pos ] = Min이 된다

만약 일치하지 않는다면 수정이 필요하므로

DP[ t ][ pos ] = Min + 1이 된다.

위의 내용을 코드로 작성하면 아래와 같다.

int Min = DP[t-1][pos]; //제자리에 머물렀을 경우
for(int i = 0; i<Edge[pos].size(); i++)
	Min = min(Min, DP[t-1][Edge[pos][i]]); //인접한 정점에서 왔을 경우  
if(pos != gps_log[t-1]) //주어진 경로와 다를 경우
	DP[t][pos] = Min + 1; //수정해야하므로 + 1
else DP[t][pos] = Min;

 

같은 방식으로 t가 k가 될때까지의 DP값을 구한 뒤,

DP[ k ][ 주어진 마지막 위치 ] 가 처음에 초기화한 값인 INF보다 크거나 같다면, 해당 위치에는 도달할 수 없다는 뜻이므로 answer = - 1이 된다.

 

k 는 최대 100 이므로 모든 경로를 수정한다고 해도 98회의 수정이 발생한다.

그래서 INF 값은 100보다 큰 수로 초기화 시켜주면 된다.

 

코드 작성

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000;
const int MAX_N = 200 + 5;
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log){
    int answer = 0;
    vector<int> Edge[MAX_N];
    vector<vector<int>> DP(k + 1, vector<int>(n + 1, INF));
    for(auto list : edge_list){
        Edge[list[0]].push_back(list[1]);
        Edge[list[1]].push_back(list[0]);
    }
    DP[1][gps_log[0]] = 0; //시작점은 수정이 불가능
    for(int t = 2; t<=k; t++){ //시간
        for(int pos = 1; pos <= n; pos++){ //모든 정점 순회
            int Min = DP[t-1][pos]; //제자리에 머물렀을 경우
            for(int i = 0; i<Edge[pos].size(); i++)
                Min = min(Min, DP[t-1][Edge[pos][i]]); //인접한 정점에서 왔을 경우
            
            if(pos != gps_log[t-1]) //주어진 경로와 다를 경우
                DP[t][pos] = Min + 1; //수정해야하므로 + 1
            else DP[t][pos] = Min;
        }
    }
    
    answer = DP[k][gps_log[k-1]];
    if(answer >= INF)
        answer = -1;
    return answer;
}

//전역변수를 사용할 시 함수 내에서 초기화하는 코드가 있어야 한다.

라는 경고문이 있었지만 무시하고 Edge 벡터를 전역변수를 선언했다가 계속 틀렸다..

도저히 어디가 틀렸는지 못찾다가 혹시나 해서 지역변수로 선언했더니 맞혔다.

다음부터는 하라는 대로 하자.