백준 1446. 지름길

지름길

다익스트라, DP 문제

다익스트라로 풀이해봄

1. 간단 설명

---

사다리 게임이 생각나는 지름길 문제

0에서 D까지 최단경로 구하는 문제다

2. 예시

---

5 150 : 지름길 5개, 목적지 거리 150
0 50 10 : 0에서 출발해서 50에 도착하는 지름길. 길이는 10
0 50 20 
50 100 10
100 151 10
110 140 90 : 이게 지름길? 거리가 늘어나는 지름길도 존재함

거리의 최소값은 0-50 (10) + 50-100(10) + 50(지름길 안탐) 으로 70이다

주의사항

고속도로 역주행은 불가능

3. 알고리즘

---

지름길의 길이가 모두 양수이므로, 다익스트라를 이용해봤다

dist[D+1] 까지 놓고

dist[x] 에 도달하는 최단 경로를 구해나간다

먼저 각 도로 x는 x-1과 x+1에 1 거리만큼 떨어져 있다

즉 고속도로는 거리가 1인 쭉 연결된 그래프다

그런데, 그 사이를 연결해주는 지름길이 중간중간 존재하는 그래프다

이를 이용해 다익스트라를 돌린다

1. N, D를 입력받는다
	- 입력받을때 필요 없는 데이터는 쳐내도 됨
2. 맵 연결 정보를 담은 그래프를 만든다
	2-1. 0~D까지 i는 i+1과 1의 거리를 가진다고 저장해둠
	2-2. 지름길 정보를 N개 입력받는다
3. 0번부터 시작해서 다익스트라를 돌린다
	3-1. 큐의 맨 앞에서 노드를 꺼낸다. 더이상 꺼낼 수 없을때 까지 반복한다
	3-2. 이 노드와 연결된 노드를 찾는다
	3-3. 현재 저장된 거리 + 다음 노드에 도달하는 거리와, 다음 노드의 기록된 최단거리를 비교한다
	3-4. 만약 짧다면, 이를 기록하고, 큐에 넣는다
4. 목적지까지 도달하는 최단경로 dist[D]를 출력한다

4. 소스코드

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, D;
vector< vector<pair<int, int> > > path;
vector<int> dist;

struct Compare { // 사용자 정의 비교 연산을 위한 구조체
	bool operator()(pair<int, int> a, pair<int, int> b) { // () 연산자를 오버로딩한 함수
		// 우선순위가 낮으면 true, 높으면 false다
		if (a.first != b.first) {
			return a.first > b.first;
		}
		return a.second < b.second;
	}
};

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> D;
	
	path.resize(D + 1);
	// 맵 연결. 모든 경로들은 다음 경로와 1의 거리로 연결되어있음 
	for (int i = 0; i < D; i++) {
		path[i].push_back({ i + 1, 1 });
	}
	// 지름길 정보 입력받기
	for (int i = 0; i < N; i++) {
		int start, end, len;
		cin >> start >> end >> len;
		if (end > D) continue; // 도착지를 초과하는 경로는 따로 저장하지 않음
		path[start].push_back({ end,len });
	}
}

void Dijkstra(int start) {
	dist.resize(D + 1, 21e8); 	
	dist[start] = 0;
	priority_queue< pair<int, int>, vector<pair<int, int>>, Compare > pq;
	pq.push({ 0, 0 });

	while (!pq.empty()) {
		int now = pq.top().first;
		int now_dist = pq.top().second;
		pq.pop();

		// 현재 노드에서 연결된 길들 찾기
		for (int i = 0; i < path[now].size(); i++) {
			int next = path[now][i].first;
			int next_dist = path[now][i].second;

			// 기록해둔 경로보다 짧다면
			if (now_dist + next_dist < dist[next]) {
				dist[next] = now_dist + next_dist;
				pq.push({ next, now_dist + next_dist});
			}
		}
	}
}

int main() {
	Input();
	
	Dijkstra(0);

	cout << dist[D];

	return 0;
}

우선순위 큐를 사용자 정의 비교함수를 통해 최소힙으로 구현하였다

근데 문제 풀이에는 최대, 최소힙 둘다 패스되는것 같다

여튼 요 내용은 따로 포스팅할 예정