[프로그래머스] GPS(C++)
by atomic0x90 (Yujun Han)
[프로그래머스] 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로 생각하는 게 매우 힘들었다.
문제 풀이
- 거점과 거점 간 도로를 연결한다.(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]);
}
- 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() 값으로 초기화 했다.
- 승차 위치는 오류가 없으므로 고정값이다.
- 0초에 출발 거점(gps_log[0])을 dp에 설정
dp[0][gps_log[0]] = 0; //오류 수정 값(0)
- 0초에 출발 거점(gps_log[0])을 dp에 설정
- 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));
- (i)시간에 (j)거점을 가려고 할 때 (i-1)시간에 (j)거점에 있었는지 확인, 최솟값 선택
- 거점 개수(n) 만큼 반복
- 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()];
}
감사합니다.
홈으로 가기 | 더 많은 programmers post 보기 | post 목록 보기 |
---|---|---|