[프로그래머스/Level 3/C++/2017 카카오 코드 본선] GPS

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

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- 개발자 Jay-G는 수집한 이동 경로의 오류를 최소한으로 수정하여 좀 더 정확한 이동 경로를 구하고 싶어 한다.

택시는 다음과 같은 조건으로만 이동한다.

- 먼저 택시는 거점을 이동해 다니며, 거점 간의 이동은 해당하는 도로가 있는 경우에만 가능하다. 또한, 교통 상황에 따라 택시는 한 거점에 머무를 수 있고, 왔던 길을 되돌아갈 수 있다. 모든 도로는 방향이 별도로 없는 왕복 도로이다.

- 예를 들어, 위 그래프에서 택시가 다음과 같이 시간대별로 이동 경로를 보내왔다.

t	1	2	3	4	5	6
위치	1	2	3	4	6	7

 

- 하지만 위의 택시가 보내온 경로에는 거점 3에서 거점 6으로 이동할 수 있는 도로가 없으므로 이동 경로에 오류가 있다.

- 이러한 오류를 최소한으로 수정하여 이동 가능한 경로로 만들고 싶다. 이 경우 1회의 오류를 수정하여 다음과 같이 이동 가능한 경로를 만들 수 있다. 시간 t=4의 위치를 거점 5로 한 번 수정하면 이동 가능한 경로가 된다.

 

t	1	2	3	4	5	6
위치	1	2	3	5	6	7

- 이와 비슷하게 시간 t=4의 위치를 거점 4로 바꾸거나, 시간 t=5 위치를 거점 5로 바꾸면 이동 가능한 경로로 만들 수 있다. 위의 경우 수정한 오류의 개수는 1개이다.

 

t	1	2	3	4	5	6
위치	1	2	3	4	6	7

 

t	1	2	3	4	5	6
위치	1	2	3	3	5	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의 시작 거점과 도착 거점은 바뀔 수 없다.

 

[문제 풀이]

생각보다 접근법을 떠올리기 힘든 문제였다.

 

결국 필자도 어떻게 시작해야될지 감이 안잡혀서 힌트를 보았고, 힌트를 보고도 쉽게 떠오르지 않았던 문제였다.

 

일단 이 문제는 dp(dynamic programming)을 이용하여 풀 수 있다.

 

먼저, 항상 그런듯 dp배열의 값을 정의하고 시작하자.

 

"dp[i][j] = i번째 순서에 j노드가 올 때 , gps_log에서 0번째부터 i번째 까지 경로가 수정된 최소 횟수"

 

음... 이렇게 설명하는게 맞을지 잘 모르겠지만 밑에 그림 설명을 통해 더 자세히 알아보자.

 

먼저 dp배열에서 i를 의미하는 것은 gps_log 상에서의 인덱스를 의미하고, j는 노드들의 번호를 의미한다.

따라서 문제에서 주어진 예제를 통해 행이 6개, 열이 8개인 배열을 만들어 생각해보자(노드번호는 1부터 시작함으로 한개 더 추가해야됨)

 

0번 노드는 없으니 0번 열은 사용하지 않는다. 처음에 dp배열은 INF값으로 초기화 해준다.

 

문제에서 시작지점과 도착지점은 오류가 나지 않는다고 했으니, gps_log배열에서의 첫번째 원소 [0] 은 항상 고정이다.

다음으로 1번 행을 살펴 볼 것이다.

 

여기서 dp[i][j] 의 값은 i번째의 j번 노드가 올 때 앞선 경로가 수정된 최소 횟수를 의미한다. 따라서 gps_log[i-1]에서 gps_log[i]로 일단 갈 수 있어야 한다.

 

따라서 위의 경우 gps_log[0] = 1이므로 1에서 갈 수 있는 곳은, 문제 예제를 보면 2번과 3번 노드를 갈 수 있다. 또한 제자리에 있어도 상관없긴때문에 [1,2,3]으로 갈 수 있다.

 

이때 gps[1] = 2 이기 때문에 1번 index에 2번 노드를 놓는경우에는 수정할 필요가 없다. 하지만 1번 index에 1번 노드가 3번 노드를 놓게 되면 수정이 필요하기 때문에 값을 하나 증가시켜 넣어준다.

다음의 과정들도 차례대로 해주면 된다.

(1번예제)

이때의 답은 dp[5][7]이 되고, 만약 이 값이 INF라면 -1을 리턴해주면 된다. 왜냐하면 마지막까지 갈 수 없기 때문에

 

[소스 코드]

#include <vector>

#define INF 987654321

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    int answer = 0;
    
    vector<vector<int>> adj_list; adj_list.resize(n+1);
    vector<vector<int>> dp; dp.resize(k);
    for(int i=0; i<k; i++) dp[i].resize(n+1);
    
    for(int i=0; i<m; i++)
    {
        adj_list[edge_list[i][0]].push_back(edge_list[i][1]);
        adj_list[edge_list[i][1]].push_back(edge_list[i][0]);
    }
    
    for(int i=0; i<k; i++)
        for(int j=0; j<n+1; j++) dp[i][j] = INF;
    
    dp[0][gps_log[0]] = 0;
    for(int i=1; i<k; i++)
    {
        for(int j=1; j<=n; j++)
        {
            dp[i][j] = min(dp[i][j], dp[i-1][j]);
            
            for(int k=0; k<adj_list[j].size(); k++)
            {
                dp[i][j] = min(dp[i][j], dp[i-1][adj_list[j][k]]);
            }
            if(gps_log[i] != j) dp[i][j]++;
        }
    }
    
    if(dp[k-1][gps_log[k-1]] != INF) return dp[k-1][gps_log[k-1]];
    else return -1;
}

굳