[백준][C++] 1446번: 지름길 풀이

 

https://www.acmicpc.net/problem/1446

1446번: 지름길

 

지나야하는 고속도로에서 지름길이 있을 때 운전해야 하는 거리의 최솟값을 구하는 문제이다.

 

최소 거리를 구해야 하므로 먼저 다익스트라 알고리즘이 생각났다. 다익스트라에 대해서는 아래 블로그로 공부하였다.

https://blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

 

다익스트라 알고리즘은 동적 프로그래밍을 기반으로 하나의 정점에서 모든 정점까지의 최소 비용을 구하는 것이다.

 

풀이를 위해 자료 구조로는 0~D 까지 D+1개의 정점을 가지고 i와 i+1 사이에는 길이가 1인 간선으로 그래프를 사용했고 지름길을 저장하기 위해서는 이차원 벡터를 사용했다.

역주행할 수 없기에 지름길이 있더라도 지름길의 도착 지점과 가까운 정점은 지름길을 이용할 수가 없다. 따라서 0부터 D까지의 최단 경로를 전부 다 0부터 D값으로 초기화했다.

그러면 0부터 D까지 지름길의 도착점까지의 최소 거리가 지름길의 시작점까지의 최소 거리와 지름길의 길이를 합한 것보다 크면 갱신을 해줬다.

여기서 갱신을 했다고 끝나는게 아니다.

만약 지름길로 와서 50까지의 최소 비용이 10일 때 51까지의 최소 비용은 아직 51이므로 이 부분도 갱신을 해줘야 한다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int,int>> sc[10001]; // 지름길 저장 
int v[10001];

int min(int a, int b) {
	if(a<b) return a;
	else return b;
}

int main(void) {
	int N, D, s, e, d;
	cin >> N >> D;
	
	for(int i=0; i<N; i++) {
		cin >> s >> e >> d;
		sc[s].push_back(make_pair(e,d));
	}
	
	// 0~D 까지 D+1개의 정점을 가지는 그래프
	// i와 i+1사이에는 길이가 1인 간선 
	for(int i=0; i<10001; i++) {
		v[i] = i;
	}
	
	for(int i=0; i<=D; i++) {
		// 지름길로 왔다면 다음 경로도 갱신 
		if(i!=0) v[i] = min(v[i], v[i-1]+1);
	
		for(int j=0; j<sc[i].size(); j++) {
			if(v[sc[i][j].first] > v[i] + sc[i][j].second) {
				v[sc[i][j].first] = v[i] + sc[i][j].second;
			}
		}
	}
	
	cout << v[D];
}