오늘 풀어볼 문제는 프로그래머스의 GPS 입니다.
⭐문제링크
1. 문제설명
- 택시의 GPS가 고장이나, 정확한 이동경로가 나오지 않음. 그러나 손님의 승하차 위치는 정확함
- 택시의 GPS 로그 중에서, 정확한 이동경로로 수정하는 최소 횟수를 구하는 문제.
- 택시는 다음과 같이 움직임
- 택시는 멈출 수 있다.
- 왔던 길을 되돌아 갈 수도 있다.
- 한 거점에 머무를 수 있다.
2. 내가 한 접근
해당 문제를 보고 처음엔 이런 식으로 로직을 짰었음
[ 로직 생각 ]
1. 택시의 이동 경로를 따라 앞과 뒤에서 투 포인터로 갈 수 없는 경로 파악
1.1 갈 수 없는 경로? 현재 거점이 이전 거점으로부터 움직임의 횟수가 2 이상인 것
- 투 포인터의 두 거점의 거리차를 계산
2.1 움직임의 횟수가 2번이라면, 중간 지점 1개만 넣어주면 된단 의미
- 시작점에서 시작한 첫 번째 포인터는 본인 포함 후 인덱스 +로 두 지점의 거리차 인덱스까지 조사해서 경우의 수 구하기
- 끝에서 시작한 첫 번째 포인터는 본인 포함 후 인덱스 -로 두 지점의 거리차 인덱스까지 조사해서 경우의 수 구하기
- 3과 4에서 구한 경우의 수 중 가장 최소의 수가 정답.
[ 함수 ]
3과 4구현 위해 다익스트라가 생각남.
그러나 내 로직이 틀린 점은 다음과 같음
❌투 포인터를 사용하는 것은 옳지 않음
- 경로 수정은 전역적인 영향을 미침(한 지점을 수정하면 그 뒤 경로가 모두 변하게 됨)
- 투 포인터는 부분적인 비교에 적합하지만, 전체적인 최적 경로 수정에는 적절하지 않음
❌거리 기반 수정 방식은 문제의 본질이 아님.
- 단순히 거리차를 계산하고 중간에 하나를 넣으면 해결된다. 는 모든 경우에 적용되지 않음.
❌다익스트라를 사용하는 것은 효율적이지 않음
- 현재 가중치가 모두 같기에, 다익스트라가 아닌 DP접근이 적합함.
3. 올바른 문제 접근
해당 문제는 DP임!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
- dp[i][j] -> i번째 시간대에 j번 거점에 도착하는 최소 수정 횟수
[로직 설계]
1. 이중 for문을 돎
- 첫 번째 for 문: 시간의 흐름
- 두 번째 for 문: 모든 노드 접근 후 로직 수행
- 각 시간대(i)마다 가능한 모든 이동을 고려.
2.1 제자리에 머무르는 경우
2.2 인접 노드로 이동할 경우
이동을 고려하는 로직은 다음과 같음
(참고로 시작점을 제외한 모든 dp 배열의 값은 Integer.MAX_VALUE임)
(참고로2 해당 코드는 택시가 머무를 경우에 대한 로직임)
dp[time][cur] = Math.min(dp[time][cur],
dp[i - 1][cur] + (gps_log[time] == cur ? 0 : 1));현재 시각의 접근한 노드의 DP 배열은 다음 두 값중 작은 값을 넣어주면서 갱신되어감
- 현재 시각의 접근한 노드의 원래 DP배열 값
- 이전 시간에서 접근한 해당 노드의 값 + 현재 접근한 노드가 GPS 상에서 올바르게 찍혀있었는지(맞으면 0, 아니면 1)
위 코드는 택시가 머무를 경우의 로직이었지만, 택시가 인접 노드로 움직일 경우 위와 동일한 코드로 인접한 모든 노드의 DP값을 갱신해주면서 가면 최종적으로는 모든 DP배열이 특정 시간까지 쌓인 최소 수정 횟수를 알 수 있음
- 최종적으로 dp[k-1]gps_log[k-1]] 가 정답임.
4. 코드
import java.util.*;
class Solution {
static List<Integer>[] graph;
public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
graph = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int from = edge_list[i][0];
int to = edge_list[i][1];
graph[from].add(to);
graph[to].add(from);
}
return findRetouch(n, k, gps_log);
}
static int findRetouch(int n, int k, int[] gps_log) {
int[][] dp = new int[k][n + 1]; //i번째 시간대에 j번 거점에 도착했을 당시 수정된 횟수
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
dp[0][gps_log[0]] = 0; // 시작 지점 설정
for (int time = 1; time < k; time++) {
for (int cur = 1; cur <= n; cur++) {
if (dp[time - 1][cur] == Integer.MAX_VALUE) continue; // 이전에 도달할 수 없던 경우 패스
// 1️⃣ 제자리에 머무르는 경우
dp[time][cur] = Math.min(dp[time][cur], dp[i - 1][cur] + (gps_log[time] == cur ? 0 : 1));
// 2️⃣ 인접한 노드로 이동하는 경우
for (int next : graph[cur]) {
dp[time][next] = Math.min(dp[time][next], dp[i - 1][cur] + (gps_log[time] == next ? 0 : 1));
}
}
}
int answer = dp[k - 1][gps_log[k - 1]];
return answer == Integer.MAX_VALUE ? -1 : answer;
}
}
