[프로그래머스 Level.3] GPS (2017 카카오코드 본선) (Java)
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/1837
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코딩테스트 연습 > 2017 카카오코드 본선 > GPS
문제 설명
GPS
카카오 택시 개발자 Jay-G는 다음 업데이트를 준비하기 위해 개선사항을 위한 여러 피드백을 받았다. 그중에서 손님이 자주 탑승하는 위치를 추천해주었으면 한다는 의견이 많았다.
다음 업데이트 준비를 위해 Jay-G는 택시의 승하차 및 이동 경로를 수집하여 분석하기 시작하였다. 데이터를 분석하던 Jay-G는 몇 가지 특이사항을 발견했다. 택시의 이동 경로를 GPS를 통해 수집하게 되는데, GPS 신호 불량, 통신 오류 등 다양한 원인으로 위치의 오류가 발생한 것을 알게 되었다. 다만 승차 위치와 하차 위치는 오류가 없는 것으로 확인이 되었다.
개발자 Jay-G는 수집한 이동 경로의 오류를 최소한으로 수정하여 좀 더 정확한 이동 경로를 구하고 싶어 한다.
택시는 다음과 같은 조건으로만 이동한다. 먼저 택시는 거점을 이동해 다니며, 거점 간의 이동은 해당하는 도로가 있는 경우에만 가능하다. 또한, 교통 상황에 따라 택시는 한 거점에 머무를 수 있고, 왔던 길을 되돌아갈 수 있다. 모든 도로는 방향이 별도로 없는 왕복 도로이다.
예를 들어, 위 그래프에서 택시가 다음과 같이 시간대별로 이동 경로를 보내왔다.
| t | 위치 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 3 |
| 5 | 6 |
| 6 | 7 |
하지만 위의 택시가 보내온 경로에는 거점 3에서 거점 6으로 이동할 수 있는 도로가 없으므로 이동 경로에 오류가 있다.
이러한 오류를 최소한으로 수정하여 이동 가능한 경로로 만들고 싶다. 이 경우 1회의 오류를 수정하여 다음과 같이 이동 가능한 경로를 만들 수 있다. 시간 t=4의 위치를 거점 5로 한 번 수정하면 이동 가능한 경로가 된다.
| t | 위치 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 6 |
| 6 | 7 |
이와 비슷하게 시간 t=4의 위치를 거점 4로 바꾸거나, 시간 t=5 위치를 거점 5로 바꾸면 이동 가능한 경로로 만들 수 있다. 위의 경우 수정한 오류의 개수는 1개이다.
| t | 위치 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 6 |
| 6 | 7 |
| t | 위치 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 3 |
| 5 | 5 |
| 6 | 7 |
위와 같이 택시가 보내온 경로에서 이동 가능한 경로로 만드는 최소의 오류 수정 횟수를 구하여라.
입력 형식
주어지는 입력은 총 다섯 가지로, 거점 개수 n과 도로의 개수 m, 각 거점 간의 연결된 도로 정보 edge_list, 택시가 시간대별로 보내오는 거점 정보의 총 개수 k, 그리고 머물렀던 거점의 정보 gps_log이다. 제한조건은 아래와 같다.
- 2 <= n <= 200
- 1 <= m <= 10,000
- 2 <= k <= 100
- edge_list는 m × 2 크기의 2차원 배열로, 각 행의 두 값은 도로가 잇는 두 거점의 번호를 의미한다.
- 거점의 번호는 1부터 n까지 숫자이다.
- 모든 도로는 양방향 통행이 가능하다.
- 입력되는 데이터에서 항상 모든 거점 간 경로가 있음이 보장되지 않는다.
- gps_log의 시작 거점과 도착 거점은 바뀔 수 없다.
출력 형식
이동 가능한 경로로 만들 수 있는 최소의 오류 수정 횟수를 리턴한다. 올바른 경로로 수정하는 것이 불가능할 경우 -1을 리턴한다.
예제 입출력
| 변수명 | 값 |
| n | 7 |
| m | 10 |
| edge_list | [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 6], [5, 6], [5, 7], [6, 7]] |
| k | 6 |
| gps_log | [1, 2, 3, 3, 6, 7] |
| answer | 1 |
| 변수명 | 값 |
| n | 7 |
| m | 10 |
| edge_list | [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 6], [5, 6], [5, 7], [6, 7]] |
| k | 6 |
| gps_log | [1, 2, 4, 6, 5, 7] |
| answer | 0 |
예제에 대한 설명
두 예제 모두 edge_list의 데이터는 본문의 그림과 같은 예이다.
첫 번째 테스트 케이스에서 gps_log로 주어진 경로 중 거점 3에서 거점 6으로 가는 도로가 없다. 여기서 시간 t=4의 위치를 거점 5로 한 번 수정하면 이동 가능한 경로가 된다.
두 번째 테스트 케이스는 gps_log로 주어진 경로가 모두 도로로 연결된 경우이므로 수정이 필요 없다.
나의 코드
class Solution {
public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
int answer = 0;
int INF = 1000000;
boolean[][] roads = new boolean[n + 1][n + 1];
for(int i=0; i<edge_list.length; i++) {
roads[edge_list[i][0]][edge_list[i][1]] = true;
roads[edge_list[i][1]][edge_list[i][0]] = true;
}
// dp[i][j] = N은 gps_log의 i번째 인덱스에 j가 온다면 0번 인덱스부터 i번째 인덱스까지 총 N번 다르다.
int dp[][] = new int[k][n + 1];
// dp를 전부 INF로 초기화
for(int i=0; i<k; i++) {
for(int j=0; j<n+1; j++) {
dp[i][j] = INF;
}
}
// 처음 시작 gps_log[0]으로 고정
dp[0][gps_log[0]] = 0;
for(int i=1; i<k; i++) {
for(int j=1; j<n+1; j++) {
dp[i][j] = Math.min(dp[i][j], dp[i-1][j]); // 이동을 하지 않을 경우 먼저 확인
for(int node=1; node<n+1; node++) { // 이동을 할 경우
if(roads[j][node]) { // j노드와 연결된 노드를 확인하고 그 노드들로부터 j로 가는 모든 경우 확인
dp[i][j] = Math.min(dp[i][j], dp[i-1][node]); // j와 연결된 노드들로부터 j로 가는 최솟값으로 업데이트
}
}
// j노드가 gps_log[i]와 다르다면 gps_log를 수정해야 하기 때문에 값을 더해줌
if(j != gps_log[i]) dp[i][j]++;
}
}
answer = dp[k-1][gps_log[k-1]];
if(answer >= INF) return -1;
return answer;
}
}
풀이
- DP 문제로 풀이를 생각하기 매우 어려운 문제여서 다른 사람의 풀이를 참고하여 풀었다.
- 2차원 배열 dp를 생성한다. dp[i][j]는 gps_log의 i번 인덱스에 j 거점(노드)일 경우에 변경해야 하는 횟수를 말한다. 따라서 dp의 길이는 [k = gps_log.length][n+1]로 한다. n+1로 하는 이유는 0인덱스를 사용 하지않고 1부터 n까지 인덱스를 노드 번호로 사용하기 위해서이다.
- 이제 연결된 거점을 나타내기 위해 2차원 배열 roads를 생성하고 주어진 edge_list를 순회하면서 연결된 거점은 true로 저장한다.
- 최솟값을 구하기 위해 dp를 전부 나올 수 없는 큰 수로 초기화 하고 첫 거점의 시작인 gps_log의 0인덱스인 dp[0][gps_log[0]]의 값을 0으로 한다. (처음 시작 부분 고정)
- 이제 3중 for문을 이용하여 dp를 업데이트 해나가며 dp[k-1][gps_log[k-1]]까지 구하도록 한다.
- dp[i][j]를 구하기 위함이므로 첫 번째 for문은 1부터 k-1까지 순회하고 두 번째 for문은 1부터 n까지 순회하도록 한다.
- 우선 dp[i][j]에 전부 바로 이전 인덱스에서 거점을 이동하지 않는 경우인 dp[i-1][j]를 dp[i][j]와 비교하여 작은 것으로 저장한다. (거점을 이동하지 않고 그대로 있는 경우 확인)
- 그 후에 세 번째 for문을 진행한다. 세 번째 for문 또한 노드를 전부(1 ~ n) 순회하도록 한다.
- 현재 dp[i][j]를 구하는 중이므로 gps_log의 i번 인덱스에 j 거점(노드)일 경우를 구하는 것이기 때문에 노드를 전부 확인하며 roads에 저장된 연결 정보를 확인해서 j와 연결된 노드를 구해 해당 노드에서 j로 오는 경우(dp[i-1][j와 연결된 노드])를 구해 dp[i][j]와 비교하여 업데이트 한다. (연결된 거점에서 j로 온 경우 확인)
- 그리고 나서 dp[i][j]의 j가 gps_log[i]와 다르다면 gps_log를 수정해주어야 하기 때문에 dp[i][j]를 1 증가시킨다.
- 이렇게 모든 for문을 돌고 나서 최종적으로 구하려고 했던 dp[k-1][gps_log[k-1]]를 확인해서 해당 값이 처음에 초기화했던 큰 수라면 올바른 경로로 수정하는 것이 불가능하다는 것이므로 -1을 반환하고 아니라면 answer를 반환하면 된다.