[프로그래머스] GPS / C++
문제 설명
카카오 택시 개발자 Jay-G는 다음 업데이트를 준비하기 위해 개선사항을 위한 여러 피드백을 받았다. 그중에서 손님이 자주 탑승하는 위치를 추천해주었으면 한다는 의견이 많았다.
다음 업데이트 준비를 위해 Jay-G는 택시의 승하차 및 이동 경로를 수집하여 분석하기 시작하였다. 데이터를 분석하던 Jay-G는 몇 가지 특이사항을 발견했다. 택시의 이동 경로를 GPS를 통해 수집하게 되는데, GPS 신호 불량, 통신 오류 등 다양한 원인으로 위치의 오류가 발생한 것을 알게 되었다. 다만 승차 위치와 하차 위치는 오류가 없는 것으로 확인이 되었다.
개발자 Jay-G는 수집한 이동 경로의 오류를 최소한으로 수정하여 좀 더 정확한 이동 경로를 구하고 싶어 한다.
택시는 다음과 같은 조건으로만 이동한다. 먼저 택시는 거점을 이동해 다니며, 거점 간의 이동은 해당하는 도로가 있는 경우에만 가능하다. 또한, 교통 상황에 따라 택시는 한 거점에 머무를 수 있고, 왔던 길을 되돌아갈 수 있다. 모든 도로는 방향이 별도로 없는 왕복 도로이다.
예를 들어, 위 그래프에서 택시가 다음과 같이 시간대별로 이동 경로를 보내왔다.
t | 1 | 2 | 3 | 4 | 5 | 6 |
위치 | 1 | 2 | 3 | 3 | 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 | 3 | 6 | 7 |
t | 1 | 2 | 3 | 4 | 5 | 6 |
위치 | 1 | 2 | 3 | 3 | 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 | m | edge_list | k | gps_log | answer |
7 | 10 | [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 6], [5, 6], [5, 7], [6, 7]] |
6 | [1, 2, 3, 3, 6, 7] | 1 |
n | m | edge_list | k | gps_log | answer |
7 | 10 | [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4], [3, 5], [4, 6], [5, 6], [5, 7], [6, 7]] |
6 | [1, 2, 4, 6, 5, 7] | 0 |
코드
#include <vector>
#include <climits>
using namespace std;
vector<vector<int>> graph; // 연결된 노드 저장
vector<vector<int>> mem; // 수정 횟수 저장
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log)
{
int answer;
int i, j, g, next;
// 벡터 초기화
// clear()하지 않으면 실패하거나 core dump 발생
graph.clear();
graph.resize(n + 1, vector<int> (0));
mem.clear();
mem.resize(k + 1, vector<int> (n + 1, INT_MAX));
// 연결된 노드 저장
for (i = 1; i <= n; i++)
{
graph[i].push_back(i);
}
for (i = 0; i < edge_list.size(); i++)
{
graph[edge_list[i][0]].push_back(edge_list[i][1]);
graph[edge_list[i][1]].push_back(edge_list[i][0]);
}
// 시작 위치는 고정, 오류 없음 -> 수정 횟수 0
mem[1][gps_log.front()] = 0;
// 1번째부터 (k - 1)번째까지
for (i = 1; i < k; i++)
{
// i번째에 도달할 수 있는 노드 j에서 다음 노드로 가기 위한 수정 횟수를 저장
for (j = 1; j <= n; j++)
{
// 노드 j에 도달할 수 없으면 다음 노드로 갈 수 없음
if (mem[i][j] == INT_MAX)
continue;
// 노드 j에서 갈 수 있는 모든 노드를 확인
for (g = 0; g < graph[j].size(); g++)
{
next = graph[j][g];
// gps_log의 값과 같은 경우
if (next == gps_log[i])
mem[i + 1][next] = min(mem[i + 1][next], mem[i][j]);
// gps_log의 값과 다른 경우 (수정 필요)
else
mem[i + 1][next] = min(mem[i + 1][next], mem[i][j] + 1);
}
}
}
// k번째에 도착 위치에 가기 위한 수정 횟수
answer = mem[k][gps_log.back()];
// 도착 위치에 갈 수 없는 경우
if (answer == INT_MAX)
answer = -1;
return answer;
}
m[i][j]는 i번째로 노드 j에 도달하기 위한 수정 횟수를 의미한다. 연결된 노드에 자기 자신을 추가하는 이유는 이동하지 않고 그대로 머무르는 경우를 고려하기 위해서다. 하지만 이 부분을 추가하지 않아도 통과가 되었다.
다음은 첫 번째 입출력 예의 수행과정이다. 먼저, 출발 위치가 1이므로 mem[1][1]을 0으로 초기화한다. 행은 k번째의 노드를 의미하고, 열은 노드 n을 의미한다.
두 번째로 갈 수 있는 노드는 노드 1에 연결된 노드 2와 노드 3이다. 또한 이동하지 않고 노드 1에 그대로 머무를 수도 있다. 노드 2는 gps_log의 두 번째 노드와 같으므로 수정이 필요없지만 다른 노드들은 수정이 필요하다.
동일한 방법으로 k번째에 노드 n에 도착하기 위한 수정 횟수까지 구해준다.
링크
programmers.co.kr/learn/courses/30/lessons/1837
github.com/inbdni/Programmers/blob/master/level03/GPS.cpp