[Java] 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로 주어진 경로가 모두 도로로 연결된 경우이므로 수정이 필요 없다.

 

 

접근 방법

---

DP를 사용해 해결하였습니다. 

저는 동적계획법을 사용할 때 재귀함수를 사용한 Top-Down방식을 선호하기 때문에 Top-Down방식으로 해결하였습니다.

 

dp테이블의 설계는 아래와 같습니다.

dp[시간][지점] = 최적해(마지막 시간 부터 현재 시간까지의 거점들을 이동 가능 경로로 만들 수 있는 최소 변경 횟수)

 

 문제를 해결하기에 앞서 필요한 데이터를 전처리 해야 합니다. 저는 아래와 같은 구조로 데이터를 전처리 하였습니다.

 

ArrayList <ArrayList<Integer>> info = new ArrayList();

info[현재위치] = {현재 위치로 부터 갈 수 있는 거점들의 집합}

 

info의 초기화 코드는 아래와 같습니다.

public void init(int n, int[][] edge_list, int[] gps_log){

	this.gps_log = gps_log;
	
    //dp를 -1로 초기화
	for(int i=0;i<=gps_log.length;i++)
		Arrays.fill(dp[i], -1);

	for(int i=0;i<=n;i++){
		info.add(new ArrayList<Integer>());
		info.get(i).add(i); //정차하는 경우
	}

	for(int i=0;i<edge_list.length;i++){
		info.get(edge_list[i][0]).add(edge_list[i][1]); //양 방향
		info.get(edge_list[i][1]).add(edge_list[i][0]); //양 방향
	}
}

 

dp의 핵심 풀이는 info[현 위치]의 한 요소를 next라고 할 때 가능한 모든 next에 대해 최소를 구해가는 것이고, 

next == gps_log[현재 시간 + 1]라면 거점 정보의 변경 없음,  next != gps_log[현재 시간 + 1]라면 변경횟수 1회 증가를 하여 반환을 하면 됩니다. 자세한 설명은 소스 코드에 주석 처리 하겠습니다.

 

여기서 중요한 점은 불가능한 경우가 2가지가 있다는 점입니다.

1. edge_list에서 마지막 거점으로 가능 경로가 없는 경우

2. 마지막 거점을 변경해야지만 조건에 만족하는 경우 

 

 

소스 코드

---

import java.util.*;

class Solution {
    
    ArrayList <ArrayList<Integer>> info = new ArrayList();
    int[] gps_log;
    int[][] dp = new int[101][201];
    int MAX = 54321;
    
    public void init(int n, int[][] edge_list, int[] gps_log){
        
        this.gps_log = gps_log;
        
        for(int i=0;i<=gps_log.length;i++)
            Arrays.fill(dp[i], -1);
        
        for(int i=0;i<=n;i++){
            info.add(new ArrayList<Integer>());
            info.get(i).add(i); //정차하는 경우
        }
        
        for(int i=0;i<edge_list.length;i++){
            info.get(edge_list[i][0]).add(edge_list[i][1]); //양 방향
            info.get(edge_list[i][1]).add(edge_list[i][0]); //양 방향
        }
    }
    
        
    public int solve(int time, int now){
        
       	// 마지막 지점은 변경 불가능 이므로 1이 아닌 MAX를 return 
        if(time == gps_log.length - 1)
            return dp[time][now] = (gps_log[time] == now) ? 0 : MAX;
        //이미 구해진 최적해가 있다면
        if(dp[time][now] != -1)
            return dp[time][now];
        
        //ret는 최소를 구하기 위한 변수이므로 비교적 큰 값으로 초기화
        int ret = MAX;
        dp[time][now] = 0;
        
        for(int i=0;i<info.get(now).size();i++){
            int next = info.get(now).get(i);
            ret = Math.min(solve(time+1, next), ret);
        }
        
        //변경해야 하는 경우 +1
        return dp[time][now] = (gps_log[time] == now) ? ret : ret + 1;
    }
    
    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
        int answer = 0;
        init(n, edge_list, gps_log);
        answer = solve(0, gps_log[0]);
        
        //마지막 지점으로 가는 경로가 없거나, 만족하는 해가 없다면
        return answer = (dp[k-1][gps_log[k-1]] == -1 || dp[k-1][gps_log[k-1]] >= MAX) ? -1 : answer;
    }
}