[2017 카카오코드 본선] GPS (level3)

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

코딩테스트 연습 - GPS

 

 

[풀이방법]

DP 로 풀어보자

DP[i][j] -> i 시간에 j 로 가려면, 얼마나 수정되어야 하는지 최소의 수

DP[마지막시간][마지막점] 을 answer 로 리턴해주면 된다.

 

1. gps_log 를 기반으로 dp 를 초기화 해준다.

INF 로 다들 초기화해주고, 

DP[0][시작점] = 0; // 0시간에 시작점 변경은 안해도 되니까 고정이니까

 

2. i 시간에 j 위치에 올 수 있는 최소 변경횟수를 구하기 위해서는

    2-1. i-1 시간에서 j와 연결이 되어있는 노드들

    2-2. i-1 시간에서 위치를 변경하지 않았을 경우 (j 에 계속 위치가 되어있을 경우)

   에서 최소값을 구한 후에

   2-3. j가 원래 i 시간에 원래 가야했던 위치인지 확인을 해보고

       - 그 위치가 아니라면 i 시간에서 j로 경로가 변경이 된 것이기 떄문에 +1을 해준다.

 

 

[전체 코드]

#include <vector>
#include <iostream>
#include <map>
using namespace std;


int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    int answer = 0;
    
    map <int, vector<int>> road;
    for(auto edge : edge_list) {
        road[edge[0]].push_back(edge[1]);
        road[edge[1]].push_back(edge[0]);
    }
    
    
    vector <vector<int>> dp (k, vector <int> (n+1, 987654321));
    
    for(int i=0; i<k; i++)
        for(int j=1; j<=n; j++)
            dp[i][j] = 987654321;
    
    dp[0][gps_log[0]] = 0;
    
    // 시간
    for(int sec=1; sec<k; sec++) {
        
        for(int dest=1; dest<=n; dest++) {
            // 이동하지 않고 그 자리 에 있을 경우
            dp[sec][dest] = min(dp[sec-1][dest], dp[sec][dest]);
            // 연결되어있는 노드
            for(auto prev: road[dest]) {
                dp[sec][dest] = min(dp[sec-1][prev], dp[sec][dest]);
            }
            if(dest != gps_log[sec])
                dp[sec][dest]+=1;
        }
    }
    // 올바른 경로로 수정하는 것이 불가능할 경우 -1
    if(dp[k-1][gps_log[k-1]] >= 987654321)
        return -1;
    
    return dp[k-1][gps_log[k-1]];
}

 

[완전탐색 풀이]

테스트 케이스 맞음 그 외는 틀림 -> 아무래도 시간초과가 나는 듯함

#include <vector>
#include <map>
#include <iostream>
using namespace std;

int answer;
map <int, vector <int>> road;
vector<int> track;
vector <int> gps;

void dfs(int cur, int cnt, int target) {
    if(target == cnt) {
        int error_cnt = 0;
        // 마지막 거점은 바뀔수가 없다.
        if(track[target-1] != gps[target-1]) return;
        
        for(int i=1; i<track.size()-1; i++) 
            if(track[i] != gps[i])
                error_cnt++;
        
        answer = min(answer, error_cnt);
        return;
    } 
    
    for(auto next: road[cur]) {
        track.push_back(next);
        dfs(next, cnt+1, target);
        track.pop_back();    
    }
}


int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    
    answer = k;
    road.clear();
    track.clear();
    gps = gps_log;
    
    for(auto edge : edge_list) {
        int x = edge[0];
        int y = edge[1];
        road[x].push_back(y);
        road[y].push_back(x);
    }
    
    for(int i=1; i<=n; i++)
        road[i].push_back(i);
    
    int start = gps_log[0];
    track.push_back(start);
    dfs(start, 1, k);
    track.pop_back();
    
    if(answer >= k-2) return -1;
    
    return answer;
}