[백준] 1916번 최소비용 구하기 C++ 문제풀이

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

1916번: 최소비용 구하기

문제 풀이

최소 경로 찾기 문제에 자주 사용되는 알고리즘 2개가 있다.

1. 플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 모든 정점들간의 최단거리를 계산하는 알고리즘으로 시간복잡도가 O(N^3) 으로 크다.

2. 다익스트라 알고리즘

다익스트라 알고리즘은 한 정점으로부터 다른 모든 정점까지의 최단거리를 계산하는 알고리즘으로 O(ElogV)로 훨씬 빠르다

 

이 문제는 출발 도시와 도착 도시가 명시되어 있으므로 플로이드 워셜 알고리즘보다 다익스트라 알고리즘을 사용하는게 좋다.

1. 초기 시작점을 기준으로 갈 수 있는 점들에 대해 갱신

2. 현재 지점에서 이동 비용이 가장 적은 노드로 이동

3. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신

2, 3번의 과정을 반복해서 시작 지점에서의 최단 거리를 갱신한다.

소스 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 각각의 간선의 정보를 pair를 통해서 저장
vector<pair<int, int>> a[1001]; 
int d[1001]; //각 정점에서의 최소비용
void dijkstra(int start) {
	d[start] = 0; //시작 지점의 비용은 0;
    // priority_queue는 기본적으로 우선 순위가 높은 요소가 먼저 나오는 자료구조
	priority_queue<pair<int, int>> pq;
    //pq에 집어넣을때는 가중치를 first, 다음 노드 정보를 second에 넣음.
	pq.push(make_pair(0, start));
	//가까운 순서대로 처리하기 위해 큐를 이용
	while (!pq.empty()) {
    	//짧은 것이 먼저오게 음수화해서 저장.
		int distance = -pq.top().first; //따라서 꺼낼때는 음수화를 풀어줌
		int current = pq.top().second;
		pq.pop();
		if (d[current] < distance) continue;
		for (int i = 0; i < a[current].size(); i++) {
			//선택된 노드의 인접 노드를 탐색
			int next = a[current][i].first;
			//선택된 노드를 거쳐서 인접 노드로 가는 비용
			int nextDistance = distance + a[current][i].second;
			// 기존의 최소 비용보다 저렴하면 업데이트
			if (nextDistance < d[next]) {
				d[next] = nextDistance;
				pq.push(make_pair(-nextDistance, next));
			}
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	//초기화
	for (int i = 1; i <= n; i++) {
		d[i] = 1000000001;
	}
	//간선 정보 추가
	for (int i = 0; i < m; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		a[s].push_back(make_pair(e, w));
	}
	int st, en;
	cin >> st >> en;
	dijkstra(st);

	cout << d[en] << '\n';
}