문제
https://www.acmicpc.net/problem/1446
매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.
세준이가 운전해야 하는 거리의 최솟값을 출력하시오.
입력
첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.
출력
세준이가 운전해야 하는 거리의 최솟값을 출력하시오.
풀이
가중치가 있는 최단 경로 문제이다. 그래서 BFS는 아닐 것이고,, (BFS는 보통 가중치가 없거나 가중치가 모두 동일한 경우에 사용한다.) 한 노드에서 다른 모든 노드로 가는, 모든 노드에서 모든 노드로 가는 최단 경로를 구하는 것도 아니다. 즉, 다익스트라, 플로이드-워셜 문제도 아닌 거 같다.
구글링으로 힌트를 얻어보니 DP를 이용하는 문제였다. DP는 다음과 같은 특징을 갖고 있다.
- 최적 부분 구조 (Optimal substructure): 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
- 중복되는 부분 문제 (Overlapping subproblem): 동일한 작은 문제를 반복적으로 해결한다.
0부터 D까지 차를 타고 이동할 때 지름길을 따라가는 경우와 일반 고속도로를 따라가는 경우를 비교하여, 특정 지점까지 가는 최소 운전 거리를 dp 테이블에 저장하자. (특정 지점 i를 0부터 D까지 1씩 증가시키면서 dp 테이블 갱신)
dp 테이블에 저장한 부분 문제들의 해를 종합하면, 최종적으로 세준이가 D까지 가는 데 필요한 최소 운전 거리를 dp[D]로 구할 수 있다.
그리고 지름길의 시작 위치, 도착 위치, 지름길의 길이 정보를 입력 받을 때 유의해야 할 점이 있다.
지름길의 시작점, 도착점 사이의 거리가 원래 그 둘 사이의 고속도로 길이보다 길면, 사실상 지름길이 아니므로 해당 간선 정보는 저장할 필요가 없다. (예시 입력: 110 140 90)
그리고 문제에서 모든 지름길은 일방통행이고 고속도로를 역주행 할 수 없다고 했으므로, 지름길의 도착점이 D보다 큰 경우도 간선 정보를 저장할 필요가 없다. (예시 입력: 100 151 10)
#include <iostream>
#include <queue>
#include <vector>
#define MAX 10001
using namespace std;
// 지름길의 개수, 고속도로 길이
int N, D;
// 지름길의 위치, 거리를 저장하는 배열
vector<pair<int, int>> path[MAX];
// 특정 위치까지 가는 최단 거리를 저장하는 테이블
int dist[MAX];
void input(){
cin >> N >> D;
// i 위치까지 가는 최단 거리 초기화
for(int i = 0; i <= D; i++){
dist[i] = i;
}
for(int i = 0; i < N; i++){
// 지름길의 시작점, 도착점, 길이
int start, end, length;
cin >> start >> end >> length;
if(end > D) continue;
if(end - start <= length) continue;
path[start].push_back({end, length});
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
input();
int before;
for(int i = 0; i <= D; i++){
if(i == 0) before = -1;
else before = dist[i - 1];
// 지름길 반영한 최단 거리: dist[i]
// 일반 고속도로 이용한 거리: dist[i - 1] + 1
dist[i] = min(dist[i], before + 1);
// i 위치에서 출발하는 지름길이 없다면 무시
if(path[i].empty()) continue;
// i 위치에서 출발하는 지름길이 있다면
for(auto edge: path[i]){
int end = edge.first;
int length = edge.second;
// 최단 거리 테이블 갱신
if(dist[end] > dist[i] + length){
dist[end] = dist[i] + length;
}
}
}
// D까지 가는 최단 거리 출력
cout << dist[D] << endl;
return 0;
}
