[백준 알고리즘] 11779번 - 최소비용 구하기 2 (Dijkstra에서 경로를 출력하는 방)

1. 문제 및 예시 실행 결과

 

 간단한 다익스트라 문제이지만, 경로를 출력해야한다. 처음에는 문자열을 옮기는 방식으로 풀었는데, 원인을 알 수 없는 이유로 틀렸다는 문자만 계속 떴다. 그래서 경로를 배열에 저장하는 방식을 사용했다... 문자열도 같은 원리인데 대체 왜 그러는지 참...

 

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

11779번: 최소비용 구하기 2

---

---

2. 풀이과정

 

 문제를 잘게 나눠봤다.

 

1. 입력

2. 다익스트라 진행

3. 최단경로 출력

 

 다익스트라 함수는 기존의 함수와 같이 진행하였지만, 경로를 역추적하는 코드를 넣었고, 가지고 있는 비용이 지금 자신의 비용보다 크다면 탐색을 진행하지 않도록 하여 시간을 줄였다. 다음은 다익스트라 코드이다.

 

void dijkstra(int start) {
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	visit[start] = start;
	fare[start] = 0;
    
	while (!pq.empty()) {
		int current_node = pq.top().second;
		int current_fare = -pq.top().first;
		pq.pop();
        
        if (fare[current_node] < current_fare) continue;
        
		for (int i = 0; i < graph[current_node].size(); i++) {
			int next_node = graph[current_node][i].first;
			int next_fare = graph[current_node][i].second + current_fare;

			if (fare[next_node] > next_fare) {
				fare[next_node] = next_fare;
				visit[next_node] = current_node;
				pq.push(make_pair(-next_fare, next_node));
			}
		}

	}
}

 

 다음은 출력 코드이다. 공부도 할겸 재귀 함수로 구현해보았다.

 

void print_node(int node, int count) {
	if (start_node == node) {
		cout << count << endl;
		//cout << visit[node] << ' ';
	}
	else {

		print_node(visit[node], count + 1);
		cout << visit[node] << ' ';
	}
}

 

 다음은 전체 코드이다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#define INF 987654321

using namespace std;

vector<pair<int, int>> graph[1003];
int n, m;

//버스 요금
int fare[1003];
//경로 역추적
int visit[1003];
int start_node, end_node;

void print_node(int node, int count) {
	if (start_node == node) {
		cout << count << endl;
		//cout << visit[node] << ' ';
	}
	else {

		print_node(visit[node], count + 1);
		cout << visit[node] << ' ';
	}
}

void dijkstra(int start) {
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	visit[start] = start;
	fare[start] = 0;
    
	while (!pq.empty()) {
		int current_node = pq.top().second;
		int current_fare = -pq.top().first;
		pq.pop();
        
        if (fare[current_node] < current_fare) continue;
        
		for (int i = 0; i < graph[current_node].size(); i++) {
			int next_node = graph[current_node][i].first;
			int next_fare = graph[current_node][i].second + current_fare;

			if (fare[next_node] > next_fare) {
				fare[next_node] = next_fare;
				visit[next_node] = current_node;
				pq.push(make_pair(-next_fare, next_node));
			}
		}

	}
}

void init_fare() {
	for (int i = 1; i <= n; i++) {
		fare[i] = INF;
	}
}

int main(void) {

	int start, end, bus_fare;

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> start >> end >> bus_fare;
		graph[start].push_back(make_pair(end, bus_fare));
	}

	cin >> start_node >> end_node;

	init_fare();
	dijkstra(start_node);
	

	cout << fare[end_node] << endl;
	print_node(end_node, 1);
	cout << end_node;

	return 0;

}