백준 11779번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	골드 3

---

풀이

 이번 문제는 최단경로 문제이면서, 동시에 최단경로도 찾아야 하는 문제이다. 정점의 개수가 1천개밖에 되지 않기 때문에 플로이드 워셜, 다익스트라 모두 가능한 문제일 것이다. 아직 플로이드 워셜 최단경로 역추적을 공부하지 않아, 다익스트라 역추적을 이용해 풀어보았다. 조만간 플로이드 워셜 역추적도 공부해서 풀어보도록 하겠다.

 

 다익스트라 알고리즘에서 최단경로를 역추적하는 방법은 경로를 저장하는 배열을 하나 더 만든다. 각 배열의 인덱스는 정점 번호에 맞추고, 각 배열의 값에는 해당 정점에 오기 전에, 어느 정점을 거쳤는지를 저장한다. 코드로 설명을 하면, prev라는 배열을 선언하고, 모두 -1로 초기화를 한다. 해당 배열에 설명한 방식대로 경로를 저장고자 한다. 다익스트라 알고리즘의 구조상, 다음에 방문할 정점의 거리를 pq에 push하기 전에 갱신한다. 이때, 거리가 갱신되었다는 것은 이러한 경로로 방문을 했다는 뜻이 된다. 다음에 방문할 정점을 next, 현재 위치를 curr이라고 하자. prev[next] = curr 로 이전에 방문한 정점의 정보를 저장한다. 다익스트라를 끝마치고나면 시작정점 st에서 도착정점 ed까지의 어떠한 최단경로의 거리가 존재하며, 이는 최단경로가 존재한다는 뜻이 될 것이다. prev[ed]의 값은 ed를 방문하기 전의 정점 번호가 들어있을 것이고, 이를 계속 방문하다보면, 시작정점이 나올 것이다. 이를 역으로 출력하면 그것이 경로가 될 것이다.

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using pii = pair<int,int>;

int n, m, st, ed;
vector<vector<pii>> graph;


void input() {
	int s, e, d;
	cin >> n >> m;
	graph.resize(n + 1);

	while(m--) {
		cin >> s >> e >> d;
		graph[s].push_back({d, e});
	}

	cin >> st >> ed;
}

void sol() {
	priority_queue<pii, vector<pii>, greater<>> pq;
	int prev[n + 1], dist[n + 1];

	memset(prev, -1, sizeof(int)*(n + 1));
	fill(dist, dist+n+1, INT32_MAX);

	dist[st] = 0;
	pq.push({0, st});

	while(!pq.empty()) {
		auto [cur_d, cur_p] = pq.top(); pq.pop();

		if (cur_d > dist[cur_p]) continue;

		for(auto& [nxt_d, nxt_p] : graph[cur_p]) {
			if (dist[nxt_p] > cur_d + nxt_d) {
				dist[nxt_p] = cur_d + nxt_d;
				prev[nxt_p] = cur_p;
				pq.push({dist[nxt_p], nxt_p});
			}
		}
	}

	int r = ed;
	deque<int> route;
	
	while(1) {
		route.push_back(r);
		if (r != st) r = prev[r];
		else break;
	}

	cout << dist[ed] << endl;
	cout << route.size() << endl;
	while(!route.empty()) {
		cout << route.back() << ' ';
		route.pop_back();
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}