코딩 테스트 -- GPS - (프로그래머스 / C++)

 

프로그래머스

 

 

문제 요약

---

여러 거점과 그 거점들을 이어놓은 양방향 경로들이 존재할때, 길찾기를 통해 경로를 설정해주는 어플이 있다고합니다.

 

그런데 이 어플에  경로를 이탈하는 문제가 발생하여 이를 수정하려 하는 알고리즘을 개발하려 할때 

다음과 같은 조건을 지켜 도착지점으로 안내하도록 하는 최소한의 수정횟수를 구하는 문제!

 

1. 출발지와 도착지는 문제가없다.

2. 거점을 돌아갈수도, 머무를수도 있다.

3. 수정이 불가능할 경우 -1을 출력한다.  

 

---

 

 

문제에서 주어진 그림만 보았을때에는 DFS,BFS 탐색을 통해 경로의 수정횟수를 알아보는 문제인줄 알았습니다. 

하지만...

거점의 갯수가 최대 200 / 도로의 수는 10000으로 탐색을 하기에는 상당히 큰 데이터들의 사이즈가 문제였습니다.

 

 

그래서 첫번째로 생각한 풀이는 각 지점마다 출발지와 도착지점으로의 거리를 측정하여 가능한지부터 측정하여

경우의 수를 줄여주는 방법을 생각하였으나, 이 경우에도 측정 후

경로를 확인, 수정횟수를 세어 줘야한다는 문제가 있었습니다. 

 

 

 

그래서 생각한 방법! 

 

매번 탐색 문제인것 같지만 데이터의 량이 너무 크다 >> DP 동적계획법

 

이 문제에서 구하고자 하는것은 수정횟수,

사용할 수 있는 데이터의 종류는 시간과 거점

 

 

 

아래처럼 구성해주고 코드를 작성해 보았습니다.

DP[i][j] = i분에 j노드까지 이동했을때 최소 수정횟수 계산

 

 

 

여기까지만 생각하고 나니 코드 부분은 생각보다 쉽게 구현되었던것 같습니다.

 

 

가장 먼저 각각의 변수들을 선언해주고

각 거점이 서로 연결되었는지를,  edge_list [ n+1*n+1]의 벡터에 저장해주었습니다.  

int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    int answer = 0;
    
    int time=gps_log.size();
    
    vector<vector<int>> map(n+1,vector<int>(n+1,0));           // 연결 정보 확인
    vector<vector<int>> DP(time+1,vector<int>(n+1,987654321)); 
    
    for(vector<int> i : edge_list){
        map[i[0]][i[1]]=1;
        map[i[1]][i[0]]=1;
    }
    
    for(int i=0;i<=n;i++){
        map[i][i]=1;
    }

 

 

 

다음 출발지는 수정할 필요가 없기에 

DP[1][출발지] = 0 (수정횟수 0) 으로 선언해주고

DP[1][gps_log[0]]=0;
    
    for(int i=2;i<time+1;i++){ // 시간적 탐색
        
        for(int j=1;j<n+1;j++){
            if(DP[i-1][j]!=987654321){ // 이전시간대까지 도달할수 있었던 노드들
                for(int k=1;k<n+1;k++){
                    if(map[j][k]==1){ // 그 노드에서 넘어갈 수 있는 다음 노드들
                        if(gps_log[i-1]==k){ // 수정 x
                            DP[i][k]=min(DP[i-1][j],DP[i][k]);
                        }
                        else{
                            DP[i][k]=min(DP[i-1][j]+1,DP[i][k]);
                        }
                    }
                }
            }
        }
    }

 

 

시간순으로 탐색을 시작하는 dp코드를 작성하였습니다. 

 

순서는

1. 이전 시간대에 도달할 수 있었던 거점들을 체크하고

2. 그 거점에 연결된 거점들을 찾아준뒤

3. 현재 시간대에 연결된 거점들로 이동하는 경우와 기존 DP에 저장된 값들을 비교

+ 수정했는지도 고려하여 DP수정

 

 DP[i-1][j]+1  : 수정했을 때
 DP[i-1][j]   : 수정 안했을 때
 DP[i][j]+1	: 현재 시간대에 이미 저장되어있던 값

 

 

 

코드는 여기서 끝..... 

 

 

DP문제는 생각하기까지가 오래걸리는 문제.... 풀기에는 어렵지 않은 문제였네요

 

탐색, 재귀,경우의 수 등등의 문제에서 데이터의 값이 너무크다....?

>>> 동적 계획법도 생각해보기!

 

 

 

 

ALL

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

//>> 현재 시간,위치에서 얼마나 수정했는지가 필요하다
//물론 완탐으로도 가능하겠지만 너무 크기가 크다! 비교도 해야하니...


//DP[i][j] = i분에 j노드까지 이동했을때 최소 수정횟수 계산


// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    int answer = 0;
    
    int time=gps_log.size();
    
    vector<vector<int>> map(n+1,vector<int>(n+1,0));           // 연결 정보 확인
    vector<vector<int>> DP(time+1,vector<int>(n+1,987654321)); 
    
    for(vector<int> i : edge_list){
        map[i[0]][i[1]]=1;
        map[i[1]][i[0]]=1;
    }
    
    for(int i=0;i<=n;i++){
        map[i][i]=1;
    }
    

    DP[1][gps_log[0]]=0;
    
    for(int i=2;i<time+1;i++){ // 시간적 탐색
        
        for(int j=1;j<n+1;j++){
            if(DP[i-1][j]!=987654321){ // 이전시간대까지 도달할수 있었던 노드들
                for(int k=1;k<n+1;k++){
                    if(map[j][k]==1){ // 그 노드에서 넘어갈 수 있는 다음 노드들
                        if(gps_log[i-1]==k){ // 수정 x
                            DP[i][k]=min(DP[i-1][j],DP[i][k]);
                        }
                        else{
                            DP[i][k]=min(DP[i-1][j]+1,DP[i][k]);
                        }
                    }
                }
            }
        }
    }
    
    
    if(DP[time][gps_log.back()]==987654321){
        return -1;
    }


    return DP[time][gps_log.back()];
}

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!