[BAEKJOON] 1446번 지름길

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

문제조건

1. D킬로미터의 고속도로 길이 주어진다.
2. 지름길의 시작위치, 도착위치, 지름길의 길이가 주어진다.
3. 고속도로 끝지점까지 가는 최소거리를 구해라.

접근방법

 

Brute Force로 봐야하나,,? 평소에 잘 접하지 않은 유형의 문제여서 당황스러웠다.

최단거리를 구한다고 하면 다익스트라가 떠올랐지만 어떻게 적용시키지,,,? 계속 생각이 안나서 검색의 힘을 조금 빌렸다.

 

 Dijkstra

 

최단경로를 구하는 대표적인 알고리즘이다.이중 for문을 이용한것과, priority_queue를 이용해서 구현을 선택할 수 있는데, 우선순위 큐가 시간복잡도가 훨씬 작으므로 우선순위 큐를 사용한다.

알고리즘의 동작과정은 이와같다.

1. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택하기 위해 탐색한다.
2. 1. 에서 찾은노드를 목적지로하고 모든 노드에 대해 각각 거쳐가는 거리와 직접적인 거리를 비교해서 거쳐가는 거리가 더 작다면, 최단거리를 갱신한다.
   1. 이미 갱신된 거리에 대해서는 갱신하지 않는다.

우선순위 큐에서 최소힙 자료구조를 이용한다면 선형 탐색보다 빠른 O(log n) 시간이 나오므로, 훨씬 효율적이다. 구현또한 우선순위 큐만 선언해주면 되어서 간단하다!

---

이 문제에서 당황했던건 다익스트라 알고리즘은 떠올랐지만 적용시키기위해선, 연결된 인접리스트가 필요하다. 하지만 이 문제는 지름길의 출발지와 목적지가 연결이 안된경우도있고, 지름길을 이용하지 않고 갈 경우도 연결이 입력으로 주어지지 않았기에 까다로웠다. 해결방법은 간단하다. 내가 직접 인접리스트를 만들어주면 된다. 지름길이 아닌 그냥 고속도로에는 pair형으로 first : 최소거리, second : 도착위치 로 두어서 1단위로 모든 노드를 만들어주었다.

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define MAX 10001
using namespace std;
int n, d;


vector<pair<int,int> > path[MAX];
int dist[MAX];
void dijkstra() {
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
	// { 최소거리, 도착위치 }
	pq.push({ 0, 0 });
	dist[0] = 0;
	while (!pq.empty()) {
		pair<int, int> cur = pq.top();
		pq.pop();
		//이미 갱신된 길이
		if (cur.first > dist[cur.second]) continue;
		for (int i = 0; i < path[cur.second].size(); i++) {
			pair<int, int> next = { cur.first + path[cur.second][i].second, path[cur.second][i].first };
			if (next.first < dist[next.second]) {
				dist[next.second] = next.first;
				pq.push(next);
			}
		}
	}
}

int main(){
	cin >> n >> d;

	for (int i = 0; i < d; i++) path[i].push_back({ i + 1, 1 });

	for (int i = 0; i < n; i++) {
		int s, e, dist;
		cin >> s >> e >> dist;
		path[s].push_back({e,dist});
	}
	memset(dist, 98765432, sizeof(dist));
	dijkstra();
	cout << dist[d];
}