[백준] 11779 최소비용 구하기 2 - C++

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

---

2025.07.11 - [백준] - [백준] 1916 최소 비용 구하기 - C++

이 문제와 비슷한 문제지만? 최단거리만 출력하는게 아니라

최단거리를 지나며 경유하는 노드와 그 갯수도 출력해주어야 한다.

---

부분 코드 설명

void daik(int start) {
	dist.assign(N + 1, INF);
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > pq;
	dist[start] = 0;
	route[start] = -1; //<1>
	pq.push({ 0, start });
	while (!pq.empty()) {
		auto [cur_dist, cur] = pq.top();
		pq.pop();
		if (dist[cur] < cur_dist) {
			continue;
		}
		for (auto [next, cost] : graph[cur]) {
			if (dist[next] > cur_dist + cost) {
				dist[next] = cur_dist + cost;
				route[next] = cur; //<2>
				pq.push({ dist[next], next });
			}
		}
	}
}

서론에서 말한 문제와 비슷한 daik함수이지만, 경로를 추적하기 위해 route배열의 값을 지정한다는 것이 차이점이다.

route배열은 인덱스번째 노드를 가기 직전 방문한 노드를 값으로 저장한다.

시작점 노드는 직전 노드가 없으므로 -1을 값으로 표시해준다.

 

cout << dist[e] << "\n";
int i = e;
vector<int> route_v;
for (int i = e; i != -1; i = route[i]) { //<1>
    route_v.push_back(i);
}
cout << route_v.size() << "\n";
for (int i = route_v.size() - 1; i >= 0; i--) { //<2>
    cout << route_v[i] << " ";
}

위에서 route는 직전에 방문한 노드번호를 저장한다고 했었다.

따라서 도착노드부터 역으로 시작노드까지 가는 경로를 구해야 하니

<1>의 for문을 이용해 시작노드(=이전노드가 -1인 노드)까지 역으로 경로를 구하고, route_v vector에 저장한다.

route_v에 저장된 경로는 위에서 구한, 도착노드부터 시작노드까지의 경로이다. = 역으로 바꿔서 출력해줘야 한다.

따라서 <2>의 for문을 통해 vector의 마지막 요소부터 출력한다.

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M;
const int INF = 1e9;
vector<pair<int, int> > graph[1001]; //{거리, 번호}
vector<int> dist;
int route[1001];
void daik(int start) {
	dist.assign(N + 1, INF);
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > pq;
	dist[start] = 0;
	route[start] = -1;
	pq.push({ 0, start });
	while (!pq.empty()) {
		auto [cur_dist, cur] = pq.top();
		pq.pop();
		if (dist[cur] < cur_dist) {
			continue;
		}
		for (auto [next, cost] : graph[cur]) {
			if (dist[next] > cur_dist + cost) {
				dist[next] = cur_dist + cost;
				route[next] = cur;
				pq.push({ dist[next], next });
			}
		}
	}
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		graph[u].push_back({ v,w });
	}
	int s, e;
	cin >> s >> e;
	daik(s);
	cout << dist[e] << "\n";
	int i = e;
	vector<int> route_v;
	for (int i = e; i != -1; i = route[i]) {
		route_v.push_back(i);
	}
	cout << route_v.size() << "\n";
	for (int i = route_v.size() - 1; i >= 0; i--) {
		cout << route_v[i] << " ";
	}
	return 0;
}

---

확실히 그래프쪽이

난이도 대비 문제 티어가 높은 것 같긴 하다.

---