[프로그래머스] GPS(C++)

[프로그래머스] GPS 풀이 (2017 카카오코드 본선)

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

이 문제를 처음 봤을 때 숨이 막혔다. 문제를 어떻게 접근해야 할지 감이 안 잡혔기 때문이다.
처음 생각한 풀이는 gps_log를 순차적으로 접근하다가 오류가 발생하면 지나왔던 거점을 수정하는 방식이다. 하지만 이 방식은 경로를 한 번이라도 수정하게 되면 이전 거점을 모두 검사하고 경로를 재 탐색해야 하는 복잡하고 이상한 풀이인 것을 얼마 안 가 알게 되었다.

두 번째로 생각한 풀이는 첫 번째 방법에서 조금 바꾼 dp(dynamic programming)이다. 왜냐하면 경로를 수정하면 이전 거점을 모두 검사한다는 점에서 이전 거점에서 수정한 횟수를 최솟값으로 저장하는 메모이제이션(memoization)을 통해 풀 수 있을 것 같았다. 이걸 생각하기 위해서 많은 시간이 소요됐다.

dp 핵심 아이디어는 다음과 같다.

• dp[시간][거점 번호]
• dp 행 : 거점을 지나가는 시간
• dp 열 : 현재 시간에 도착해 있는 거점 번호

ex) dp[a][b]

현재 시간(a)에 거점(b)를 도착할 때 이전 시간(a-1)에 도착해 있는 거점으로부터 거점(b)와 연결되어 있는지 확인하고 연결되어 있으면 gps_log와 다른지 검사, 연결이 안 되어있으면 불가능

이걸 dp로 생각하는 게 매우 힘들었다.

문제 풀이

1. 거점과 거점 간 도로를 연결한다.(connect)

vector<vector<int> > connect(n+1,vector<int>());

for(int i = 0;i < edge_list.size();i++){
	connect[edge_list[i][0]].push_back(edge_list[i][1]);
	connect[edge_list[i][1]].push_back(edge_list[i][0]);
}

1. dp를 (k)행 (n+1)열로 만들고 INT_MAX - gps_log.size() 값으로 초기화 한다.

   vector<vector<int> > dp(k,vector<int>(n+1,INT_MAX - gps_log.size()));
   

   • dp는 dp[시간][거점 번호]의미를 가진다.
   • dp는 이후에 (+1) 연산을 수행하는 데 오버플로(Overflow)를 방지하기 위해서 INT_MAX - gps_log.size() 값으로 초기화 했다.
2. 승차 위치는 오류가 없으므로 고정값이다.
   • 0초에 출발 거점(gps_log[0])을 dp에 설정

     dp[0][gps_log[0]] = 0;	//오류 수정 값(0)
     

3. GPS 정보 시간(k, 시간대별로 보내오는 거점 정보의 총 개수) 만큼 반복

   for(int i = 1;i < k;i++)
   

   • 거점 개수(n) 만큼 반복

     for(int j = 1;j <= n;j++)
     

     1. (i)시간에 (j)거점을 가려고 할 때 (i-1)시간에 (j)거점에 있었는지 확인, 최솟값 선택

        dp[i][j] = min(dp[i][j],dp[i-1][j]+(gps_log[i] == j ? 0 : 1));
        

     2. (i)시간에 (j)거점을 가려고 할 때 (i-1)시간에 (j)거점과 연결되어 있는(connect[j][l])지 확인하여 현재 시간(i)에 (j)거점이 (gps_log)와 일치하는지 확인, 최솟값 선택

        for(int l = 0;l < connect[j].size();l++)
         dp[i][j] = min(dp[i][j],dp[i-1][connect[j][l]]+(gps_log[i] == j ? 0 : 1));
        

4. dp[GPS 마지막 시간][GPS 도착 거점] 이 초기값(INT_MAX - gps_log.size())인지 확인
   • 초기값이면 수정 불가(-1), 아니면 경로를 최소로 수정 한 값(dp[k-1][gps_log.back()])

정답 코드

#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
	vector<vector<int> > connect(n+1,vector<int>());

	//거점과 거점 간 도로 연결
	for(int i = 0;i < edge_list.size();i++){
		connect[edge_list[i][0]].push_back(edge_list[i][1]);
		connect[edge_list[i][1]].push_back(edge_list[i][0]);
	}

	//dp[시간][거점 번호]
	//이후에 (+1) 연산을 수행하는 데 오버플로(Overflow)를 방지하기 위해서
	//dp를 INT_MAX - gps_log.size() 값으로 초기화
	vector<vector<int> > dp(k,vector<int>(n+1,INT_MAX - gps_log.size()));

	//승차 위치는 오류가 없으므로 고정
	dp[0][gps_log[0]] = 0;

	//GPS 정보 시간(k, 시간대별로 보내오는 거점 정보의 총 개수) 만큼 반복
	for(int i = 1;i < k;i++){
		//거점 개수(n) 만큼 반복
		for(int j = 1;j <= n;j++){
			//(i)시간에 (j)거점을 가려고 할 때 (i-1)시간에 (j)거점에 있었는지 확인, 최솟값 선택
			dp[i][j] = min(dp[i][j],dp[i-1][j]+(gps_log[i] == j ? 0 : 1));

			//(i)시간에 (j)거점을 가려고 할 때 (i-1)시간에 (j)거점과 연결되어 있는(connect[j][l])를
			//확인하여 현재 시간(i)에 (j)거점이 (gps_log)와 일치하는지 확인, 최솟값 선택  
			for(int l = 0;l < connect[j].size();l++){
				dp[i][j] = min(dp[i][j],dp[i-1][connect[j][l]]+(gps_log[i] == j ? 0 : 1));
			}
		}
	}

	//dp[GPS 마지막 시간][GPS 도착 거점] 이 초기값(INT_MAX - gps_log.size())인지 확인
	//초기값이면 수정 불가(-1), 아니면 경로를 최소로 수정 한 값(dp[k-1][gps_log.back()])
	return dp[k-1][gps_log.back()] == INT_MAX-gps_log.size() ? -1 : dp[k-1][gps_log.back()];
}

감사합니다.