ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 1916 최소비용 구하기 (C++)

Posted on Feb 24, 2021 #최단 경로   #다익스트라(Dijkstra)   #Algorithm  

1916 | 최소비용 구하기

🙋‍♀️ 문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

🙌 입출력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

🙋‍♂️ 예제 입출력

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

4

🚀 코드

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

int n = 0;
int m = 0;
vector<pair<int, int>> graph[1001]; // 비용과 도착지를 한 쌍으로 벡터에 담음
// pair의 대소비교는 첫 번째 부터 이루어지므로 비용을 먼저 넣는다.

// 다익스트라 알고리즘 사용 == 그리디 + 다이나믹 프로그래밍
int dijkstra(int start, int end) {
	int i = 0;
	priority_queue <pair<int, int>> que;
	// min 힙을 이용해야 하므로, 비용을 음수값으로 넣어준다.
	vector<int> dist(n + 1, 987654321);

	dist[start] = 0;
	que.push({ 0,start });

	while (!que.empty()) {
		int cost = -que.top().first;
		int index = que.top().second; // 가장 가까운 거리를 가진 정점 번호
		que.pop();
		if (dist[index] < cost) {
			continue;
		}
		for (int i = 0; i < graph[index].size(); i++) {
			int next = graph[index][i].second;
			int nextCost = graph[index][i].first + cost;

			if (dist[next] > nextCost) {
				dist[next] = nextCost;
				que.push({ -nextCost,next });
			}
		}
	}
	return dist[end];
}

int main() {
	scanf("%d %d", &n, &m);
	int start, end, cost = 0;
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &start, &end, &cost);
		graph[start].push_back({ cost, end });
	}
	scanf("%d %d", &start, &end);

	printf("%d", dijkstra(start, end));



	return 0;
}

🌠 메모

최단경로 문제를 다익스트라 알고리즘을 이용해서 풀었다. 3학년 때 알고리즘 수업을 듣고나서 아주 오랜만에 구현을 해보게 되어서, 또 c++의 다양한 stl을 사용해서 구현한 적은 처음이라 스스로 구현하지는 못했고, 구글링을 통해 다른 사람들의 코드를 참고했다.

간만에 접해본 알고리즘이라 동작 방식으 이해하는데 상당한 시간이 걸렸다.

📌 새롭게 알게 된 점

  • INF 초기화는 987654321로 한다. 다른 임의의 수로 하면 틀릴 수 있음.
  • 벡터에 pair를 저장할 수 있다. 힙의 key, value쌍과 비슷한 개념인 것 같다. 따라서 먼저오는 first를 기준으로 정렬이 되므로 위의 경우에서는 비용을 먼저 두도록 한다. 
    vector<pair<int, int>> graph[1001];
  • 이때 각각의 원소에 대한 접근은 괄호 없이 int index = que.top().second;을 통해 할 수 있다.
  • dist배열의 초깃값은 INF이다.
  • 우선 순위 큐를 사용하면 visited배열을 사용하지 않아도 된다.
  • 우선 순위 큐는 기본적으로 max heap이므로 최소 비용을 구하기 위해서는 비용을 음수로 해서 저장해준다.

다익스트라 알고리즘의 동작 방법

  1. 가장 먼저 start 정점의 비용을 0으로 해서 dist에 삽입하고, 마찬가지로 큐에도 넣어준다.

  2. while문 안에서는(3-6의 과정), 우선 순위 큐를 사용해 비용이 가장 적게 드는 정점을 선택하고 필요시 dist배열의 값을 갱신한다.

  3. que.top()을 통해 현재 위치에서 최소 비용으로 갈 수 있는 정점을 찾아내고, 지금 방문했으므로 큐에서 제거한다.
  4. dist에 저장된 값이 cost보다 작으면 갱신할 필요가 없으므로 contineu; (사실 꼭 필요한지 모르겠다.. 아직까진 여기에 걸리는 예제를 못봤다.)
  5. 현재 위치(idx)에서 갈 수 있는 모든 정점들을 for문을 통해 방문한다. 이때 next가 idx에서 도달할 수 있는 각각의 도착 정점이고, nextCost는 현재위치 까지의 비용 + 도착 정점까지의 비용이다.
  6. 위에서 계산한 nextCost값이 저장되어 있는 dist[next]보다 작은 경우에만 그 값을 갱신하고, 큐에 해당 정점을 삽입한다.

위 과정을 반복하면 dist[end]에는 start에서 end로 갈 때의 최소 비용이 저장된다.



# 카테고리