BOJ 11779 - 최소비용 구하기 2 (다익스트라, 최단경로)

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

 

<문제설명>

다익스트라로 시작점->도착점의 최소비용을 구하고 그 경로중 아무거나 하나 출력하는 문제.

 

<풀이>

1. 일반적인풀이: 

최단경로가 갱신될때 마다 prev[next] = curr을 해준 후에 아래와 같은 방법으로 출력해준다.

stack<int> st;
int x = en;
while(x!=-1){
	st.push(x);
    x = prev[x];
}
cout << st.size() << '\n' //경로에 포함된 정점의 수
while(!st.empty()){
	cout << st.top() << " ";
    st.pop();
}

 

2. 임계경로문제 https://suuntree.tistory.com/120?category=797985

역방향 인접리스트를 하나 마련해두고 도착점부터 dfs해서 d[curr] = d[next]+wgt이면 방문해주는 방법

vector<int> ans;
bool flag = false;
void dfs(int curr) {
	if (flag) return;
	vst[curr] = true;
	ans.push_back(curr);
	if (curr == st) {
		flag = true;
		return;
	}

	for (P p : radj[curr]) {
		int next = p.first, wgt = p.second;
		if (d[curr] == d[next] + wgt && !vst[next])
			dfs(next);
	}
}

 

 

<코드> 2번방법으로 구현함

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
using namespace std;
typedef pair<int, int> P;
const int MAX = 1e3 + 3;
const int INF = 1e9;

bool vst[MAX] = { 0 };
vector<P> adj[MAX],radj[MAX];
int d[MAX], n, m, st, en;

vector<int> ans;
bool flag = false;
void dfs(int curr) {
	if (flag) return;
	vst[curr] = true;
	ans.push_back(curr);
	if (curr == st) {
		flag = true;
		return;
	}

	for (P p : radj[curr]) {
		int next = p.first, wgt = p.second;
		if (d[curr] == d[next] + wgt && !vst[next])
			dfs(next);
	}
}

int main() {
	cin >> n >> m;
	fill(d, d + MAX, INF);
	for (int i = 0,u,v,w; i < m; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({ v,w });
		radj[v].push_back({ u,w });
	}
	cin >> st >> en;

	priority_queue<P, vector<P>, greater<P>> pq; //d,v
	d[st] = 0;
	pq.push({ d[st],st });
	while (!pq.empty()) {
		int curr;
		do {
			curr = pq.top().second;
			pq.pop();
		} while (!pq.empty() && vst[curr]);
		if (vst[curr]) break;

		vst[curr] = true;

		for (P p : adj[curr]) {
			int next = p.first, wgt = p.second;
			if (d[next] > d[curr] + wgt) {
				d[next] = d[curr] + wgt;
				pq.push({ d[next], next });
			}
		}
	}
	cout << d[en] << '\n';

	fill(vst, vst + MAX, 0);
	dfs(en);

	cout << ans.size() << '\n';
	for (int i = ans.size() - 1; i >= 0; i--)
		cout << ans[i] << " ";
	cout << '\n';
}

 

 

<생각>

1번방법이 더 효율적이다. 

 

2번방법은 모든 경로에 대한 문제에서 더 효과적일 것 같다.