백준 1916 최소비용 (c++) : 피너클

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

1916번: 최소비용 구하기

 

 

다익스트라 알고리즘을 사용하는 문제다.

다익스트라 알고리즘은 그래프 문제에서 한 정점에서 모든 정점까지 최소비용이 얼마인지를 구하는 알고리즘이다.

 

int dist[1001]; // 비용

모든 정점으로의 비용을 가지는 배열이다. 처음에는 굉장히 큰 수로 초기화 된다.

다익스트라 알고리즘을 돌리며 계속해서 업데이트 해갈것이다.

void dijkstra(int start_city) {
	dist[start_city] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ start_city, 0 });
	while (!pq.empty()) {
		int now_city = pq.top().first;
		int cost = -pq.top().second;

		pq.pop();

		if (dist[now_city] < cost) continue;

		for (int i = 0; i < city[now_city].size(); i++) {
			int next_city = city[now_city][i].first;
			int next_cost = city[now_city][i].second + cost;

			if (dist[next_city] >  next_cost) {
				dist[next_city] = next_cost;
				pq.push({ next_city, -next_cost });
			}
		}
	}
}

이번에 사용하는 다익스트라 알고리즘의 전신이다. 

하나씩 확인해보자.

void dijkstra(int start_city) {
	
}

다익스트라 함수에 전해지는 변수는 시작 정점이다. 이 정점을 중심으로 모든 정점으로의 최소 비용을 구하게된다.

dist[start_city] = 0;

시작 정점의 비용은 0이다. 서울에서 서울로 가는데 걸리는 시간이 0인것과 같다.

priority_queue<pair<int, int>> pq;
pq.push({ start_city, 0 });

이번 다익스트라에선 우선순위 큐를 사용한다.

우선순위 큐는 집어넣은 값중 우선순위가 가장 높은 값을 탑으로 둔다. 

아무런 설정을 하지 않은 경우엔 높은 값을 우선순위로 둔다. 

-1과 100이 있다면 100을 우선순위로 두는 것이다.

 

우선순위 큐를 선언한뒤 {도시, 도시까지 가는데 드는 비용}을 집어넣는다.

처음에는 {시작도시, 시작도시까지 가는데 드는 비용 = 0} 을 집어넣는다.

while (!pq.empty()) {
	int now_city = pq.top().first;
	int cost = -pq.top().second;
    
    	pq.pop()

우선순위 큐가 비어있지 않은 동안 반복문을 돌린다.

int now_city에는 큐에 들어있는 우선순위가 가장 높은 도시를 집어넣는다.

int cost에는 우선순위가 가장 높은 도시까지 가는데 걸리는 비용을 집어넣는다.

int cost에서 -1을 곱한 비용을 집어넣는 이유는 뒤에서 나온다.

마지막에 pq.pop()으로 사용한 큐를 삭제해준다.

if (dist[now_city] < cost) continue;

작동시간을 줄이기 위한 코드이다. 

현재까지 업데이트된 시작도시에서 현재도시까지 가는 비용보다

현재도시까지 가는 비용이 더 높으면 뒤에있는 내용은 무시한다.

for (int i = 0; i < city[now_city].size(); i++) {
	int next_city = city[now_city][i].first;
	int next_cost = city[now_city][i].second + cost;

	if (dist[next_city] >  next_cost) {
		dist[next_city] = next_cost;
		pq.push({ next_city, -next_cost });
	}
}

현재도시에 연결된 모든 도시들을 반복문으로 돌려본다

int next_city에는 현재도시에서 갈수있는 도시를 집어넣는다.

int next_cost에는 현재도시까지의 비용과 현재도시에서 다음 도시로 가는데 드는 비용을 집어넣는다.

 

만약 현재까지 업데이트된 다음도시까지의 비용이 next_cost보다 높다면

dist[next_city]를 업데이트하고 우선순위 큐에 {도시, 도시까지의 비용 * -1}을 집어넣는다.

-1을 곱하는 이유는 비용이 낮은것을 우선순위에 둬야하기에 -1을 곱해 높은수의 우선순위는 낮추고

낮은수의 우선순위를 높이는것이다.

100에 -1을 곱해 -100으로 만들고 1에 -1을 곱해 -1로 만들면 높은수를 우선순위로 두는 큐는

-1을 -100보다 우선순위에 둘것이다.

 

위에 cost에서 -1을 곱한 값을 받는 이유가 이것이다. 들어올때 -1을 했기 때문에 다시 -1을 곱해 원래대로 되돌리는것이다.

 

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

using namespace std;

int INF = 987654321;

int n, m;
vector<pair<int, int>> city[1001];
int dist[1001]; // 비용

void dijkstra(int start_city) {
	dist[start_city] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ start_city, 0 });
	while (!pq.empty()) {
		int now_city = pq.top().first;
		int cost = -pq.top().second;

		pq.pop();

		if (dist[now_city] < cost) continue;

		for (int i = 0; i < city[now_city].size(); i++) {
			int next_city = city[now_city][i].first;
			int next_cost = city[now_city][i].second + cost;

			if (dist[next_city] >  next_cost) {
				dist[next_city] = next_cost;
				pq.push({ next_city, -next_cost });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) dist[i] = INF;

	int a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		city[a].push_back({ b, c });
	}
	cin >> a >> b;
	dijkstra(a);

	cout << dist[b] << endl;
}

전체 코드이다.