[프로그래머스, C++] GPS

문제 링크

코딩테스트 연습 - GPS

 

 

 

풀이

어렵다...

풀이를 봐도 처음에 이해하기 어려웠다.

주석으로 써놓긴 했지만 DP 문제로서 풀이는 최소 오류 수정값을 넣으면서 진행해간다.

 

// 변수들

1) adj[201];

이 변수는 한 점의 연결된 정점들을 모아둔 vector 컨테이너라고 보면된다.

201개로 설정한 이유는 정점은 1~n이므로 넘버링 되어 있기 때문이다.

ex)

adj[0] = 1, adj[0] = 2 라면 0에 연결된 점은 1과 2가 있다.

물론 문제에서는 양방향이기 때문에 adj[1] = 0, adj[2] = 0 으로 같이 연결해준다.

 

2) dp[100][201];

row는 k의 최대, col은 1~n까지의 정점들

dp[i][j]는 i가 j가 될 때, 오류 수정 횟수를 의미한다.

 

// 초기화

1) 정점 연결

2) INFINITE 값으로 초기화

 

// DP 진행

dp[i][j] = min(dp[i-1][인접 노드 정점들], dp[i-1][j]+주어진 gps_log와 같으면 0, 아니면 1)

따라서 i가 j가 될 때, 주어진 gps_log의 정점과 같으면 수정할 필요가 없으니 0을 더하고 수정하면 1을 더하는 방식으로 

정차한 경우와 정차가 아닌 경우로 나누어 최소값을 검사한다.

 

* add는 gps_log와 같아 수정해야하면 1을, 아니면 0을 더하는 변수.

1) 정차인 경우

dp[i-1][현재 정점(j)]+add와 min 비교

 

2) 정차가 아닌 경우

dp[i-1][현재 정점(j)와 연결된 점(e)]+add와 min 비교

 

// 오류 수정 최소값을 갱신하고 난 후

answer값에 INFINITE 값을 넣어놓고 마지막 도착지(gps_log.back())와 연결된 정점들에 대해서 최소 오류 수정값 중 가장 작은 값을 넣는다.

만약 k-2(수정될 최대값, 시작과 끝은 고정이므로)보다 클 경우는 -1을 저장한다.

 

이 문제는 정해진 길 안에 연결된 정점들에 한해서 최소 오류 수정값만을 구한다.

 

#include <vector>
#include <iostream>

using namespace std;

// 손님이 자주 탑승하는 위치 추천
// 승하차 위치는 오류 X
// 한 거점 머무를 수 있고 왔던 길을 되돌아가는거 가능
// 모든 도로는 왕복도로
// 거점 개수 n은 2이상 200이하
// 도로 개수 m은 1이상 10,000이하
// 연결된 정보 edge_list는 m x 2의 크기
// 거점 정보의 총 개수 k는 2이상 100이하
// 머물렀던 거점의 정보 gps_log

// DP[i][j] = min(DP[i - 1][인접 노드들], DP[i - 1][j]) + (log[i] == j ? 0 : 1)

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    const int INF = 99999999;
    int answer = INF;
    vector<int> adj[201];       // n의 최대 개수
    int dp[100][201];           // k의 최대 개수와 n의 최대 개수
        
    // 초기화
    for(int i=0; i<m; i++){
        int r = edge_list[i][0];
        int c = edge_list[i][1];
        adj[r].push_back(c);            // r과 c를 연결
        adj[c].push_back(r);            // c와 r을 연결
    }
    for(int i=0; i<100; i++){
        for(int j=0; j<201; j++){
            dp[i][j] = INF;         // INF로 초기화
        }
    }
    
    // Start
    dp[0][gps_log[0]] = 0;      // 처음은 0으로 시작
    for(int i=1; i<k-1; i++){       // 처음과 끝은 제외
        for(int j=1; j<n+1; j++){    // 1~n
            // gps_log 순서면 수정안한거니까 0, 수정했으면 1 추가
            int add = gps_log[i]==j ? 0 : 1;
            
            // 정차한 경우
            dp[i][j] = min(dp[i][j], dp[i-1][j]+add);
            
            // 정차가 아닌 연결된 점에서의 최소값을 검사
            for(auto e: adj[j]){
                dp[i][j] = min(dp[i-1][e]+add, dp[i][j]);
            }
        }
    }
    
    // 마지막 도착지와 연결된 모든 정점 검사
    int fin = gps_log.back();       // 마지막 도착지
    for(auto e: adj[fin]){
        answer = min(answer, dp[k-2][e]);
    }
    answer = (answer > k-2) ? -1 : answer;         // 최대로 수정하는 것보다 많을 경우
    
    // for(int i=0; i<k; i++){
    //     for(int j=0; j<n+1; j++){
    //         if(dp[i][j]!=INF)
    //             printf("%-6d", dp[i][j]);
    //         else
    //             printf("INF   ");
    //     }
    //     printf("\n");
    // }
    
    return answer;      // 수정 불가능: -1, 모든 연결: 0, 횟수: 최소의 오류 수정 횟수
}