<백준 알고리즘> 11779번 다익스트라 알고리즘

접근방법

1.그래프 탐색을 이용하여 출발 도시부터 도착도시까지의 최소값을 구해야 함. 그 과정에서의 경로는 어떻게 구할 것인가를 생각해봤음.
처음엔 dfs로 구현하여 만약 도착도시에 도달했을 때 그 경로가 최소일 경우 돌아오며 그 경로를 스택에 담으려 하였는데 dfs라 그런지 최단 경로를 구하려고 할경우 조건을 설정해도 시간초과가 발생했다.

2.그래서 다익스트라 알고리즘을 활용하여 탐색과정에서 최단 경로를 찾으며 만약 현재 최단거리일 경우 바로 앞의 노드를 배열에 담아 경로를 기록하고 나중에 한번에 처리하였다.

주의할점

처음에 다익스트라를 구현했을때도 시간초과가 났는데 우선순위 큐를 사용한다는 특성상 이미 탐색과정에서 최단 경로를 확인한 상태인데 또 다시 이미 방문했던 노드를 중복으로 체크하는 경우를 따로 처리하지 않아서 시간 초과가 났었다.

중복노드에 대한 처리가 중요함.
관련한 더 자세한 내용을 이 블로그에서 확인하였다.
<djm03178> 잘못 구현한 다익스트라 알고리즘 저격하기

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>

using namespace std;

int T;
int maxVal = -999;

int n, m;

vector <pair<int, int>> bus[1001];

int cost[100001] = {};
int course[1001] = {};

int startCity, endCity;

int isVisited[1001] = { 0 };




int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    cin >> n>>m;

	for (int i = 0; i < m; i++)
	{
		int start, end, cost;

		cin >> start >> end >> cost;
		
		bus[start].push_back({ end,cost });
	}
	
	fill(&cost[0], &cost[100001], 1e9);


	cin >> startCity >> endCity;

	priority_queue<pair<int, int>> q;
	cost[startCity] = 0;
	course[startCity] = 0;


	q.push({ 0,startCity });

	while (!q.empty())
	{
		int curCity = q.top().second;
		int prevCost = q.top().first;
		q.pop();

		if (prevCost > cost[curCity])
			continue;

		for (int i = 0; i < bus[curCity].size(); i++)
		{
			int nextCity = bus[curCity][i].first;
			int nextCost = bus[curCity][i].second;

			int costSoFar = prevCost + nextCost;



			if (cost[nextCity] > costSoFar)
			{
				cost[nextCity] = costSoFar;
				course[nextCity] = curCity;
				q.push({ costSoFar, nextCity });
			}
		}
	}
	
	stack <int> C;

	int fin = endCity;
	while (fin != 0)
	{
		C.push(fin);
		fin = course[fin];
	}
	
	cout << cost[endCity] << "\n";
	cout << C.size() << "\n";

	while (!C.empty())
	{
		cout << C.top() << " ";
		C.pop();
	}

    return 0;
}