[백준/C++] 1916번 최소비용 구하기

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

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째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

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

입출력 예제

소스코드

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

int n, m;
int s,e, cost;
int dist[1010];
vector<pair<int,int>> v[1010];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    /* 1 */
	cin >> n >> m; 

    /* 2 */
	for (int i = 0; i < m; i++) {
		cin >> s >> e >> cost;
		v[s].push_back(make_pair(e, cost));
	}

    /* 3 */
	cin >> s >> e;
	memset(dist, 127, sizeof(dist)); // 127은 비트연산으로 약 21억 숫자
	// or
	// fill(dist, dist + 1010, 987654321);

	/* 4 시작 노드 초기화 */
	dist[s] = 0;

	// (가중치, 도착노드)
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({ 0,s });

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

		if (dist[idx] != cost) continue;

		for (int i = 0; i < v[idx].size(); i++) {
			int next = v[idx][i].first;
			int weight = v[idx][i].second;

			if (dist[next] > dist[idx] + weight) {
				// if u -> v , dist[v] < dist[u] + w(u,v)이면 초기화할 필요 x
				dist[next] = dist[idx] + weight;
				pq.push({ dist[next],next });
			}
		}
	}
	cout << dist[e] << "\n";
	return 0;
}

문제풀이

우선, 해당 노드까지 가는데 필요한 cost를 저장할 배열 dist를 하나 선언한다. 그리고 인접리스트에 비용도 추가해서 저장해줄 벡터도 하나 선언한다. 도착 노드번호와, 노드간의 가중치를 저장해야 하므로 pair를 이용한다. 크기는 n의 범위보다 살짝 크게 해준다.

​

기본 세팅이 끝났으면 입력부터 시작하자.

1. n과 m을 입력받는다.
2. m의 크기만큼 시작노드 번호, 도착노드 번호, 가중치(비용)을 입력받아서 벡터에 저장한다.
3. 찾고자 하는 시작노드와 도착노드를 입력받고, 문제에서 나올 수 없는 큰 수로 dist 배열을 초기화해준다.
4. 시작노드는 가중치가 0이므로 초기화한다.
5. 우선 순위 큐 하나를 선언하는데, 가중치와 도착노드를 저장할 것이므로 pair로 선언하고(1번째 파라미터), 기본 컨테이너의 자료형을 pair로 바꿔준다.(2번째 파라미터) 그리고 default인 내림차순을 greater함수를 통해 오름차순으로 바꿔준다.(3번째 파라미터)
6. 다익스트라 알고리즘을 실행한다.(모양새가 bfs와 유사)
   1. pq안에 무언가 하나라도 있으면 계속 while반복
   2. top() (= 가장 가중치가 작은 것)을 꺼내와 해당 노드와 인접한 노드들을 탐색하여 최소 비용의 경로가 탐색되면( =dist[next] > dist[idx] + weight) update해준다. 그리고 update된 노드의 가중치와 노드 번호를 큐에 push한다.
   3. 자료형이 pair인데 우선순위 큐가 어떻게 우선순위를 정하냐?? -> 첫번째 인자를 기준으로 우선순위를 정한다.
7. 모든 탐색이 끝나면, dist[도착노드번호]에 도착 노드까지 가는데 필요한 최소비용이 담겨있다.

​

※ if (dist[idx] != cost) continue; 해당 코드는 mst(최소신장트리)를 만들 때는 동작하지 않는다.

mst가 생성되고 난 후, 남아있는 edge들을 큐에서 꺼낼 때 이미 처리했던 노드(=최소비용이 구해진 노드)라면 pass하는 코드이다.