[백준 1753번] C++ 최단경로

1. 문제

---

 

2. 문제 분석

---

이름에서 알 수 있듯, 방향 그래프에서의 최단 거리를 구해야 하는 문제이다.

각 edge의 가중치가 양수이므로, 다익스트라 알고리즘을 사용한다!

 

🎁 방향 그래프에서의 각 edge의 가중치가 음수도 가능하면 벨만-포드 알고리즘을 사용.

 

3. 풀이

---

다익스트라 알고리즘 풀이는 2가지 방법이 있다.

• 쉽게 구현하지만 비효율적.
• 어렵게 구현하지만 효율적.

전자는 이차원 배열을 이용해 구현하고, 후자는 우선순위 큐를 사용해 구현한다.

이 문제는 시간이 1초로 넉넉치 않으니 우선순위 큐를 사용한 구현 방법을 쓴다!

 

=> 각 노드를 보고 난 후의 거리를 저장할 dst 배열도 필요하다!

 

4. 코드

---

#include <iostream>
#include <queue>
#include <vector>

#define INF 987654321
using namespace std;

vector<pair<int, int>> V[20005];
int dst[20005];	// 각 노드를 보고난 후 최단 거리 저장하는 배열 dst.

void dijkstra(int startNode)
{
	// {비용, 목적지} 를 저장하는 우선순위 큐.
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	
	// 시작점은 비용이 0이므로 {0, startNode} 저장.
	pq.push({ 0, startNode });
	dst[startNode] = 0;

	while (!pq.empty())
	{
		pair<int, int> p = pq.top();
		pq.pop();

		// p.first : 목적지로 가는 edge의 가중치, p.second : 목적지
		for (int i = 0; i < V[p.second].size(); i++)
		{
			// 목적지에 연결된 모든 edge에 대해 cost 정보 갱신.
			int cost = V[p.second][i].first;
			int next = V[p.second][i].second;

			if (p.first + cost < dst[next])
			{
				dst[next] = p.first + cost;
				pq.push({ dst[next], next });
			}
		}
	}
}

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

	int v, e, start;
	cin >> v >> e >> start;

	int a, b, c;
	
	for (int i = 0; i < e; i++)
	{
		cin >> a >> b >> c;

		// a에서 출발하여 c의 cost를 갖고 b로 향하는 edge를 저장.
		V[a].push_back({ c, b });
	}

	for (int i = 1; i < v + 1; i++)
	{
		dst[i] = INF;
	}

	dijkstra(start);

	for (int i = 1; i < v + 1; i++)
	{
		if (dst[i] == INF)
			cout << "INF\n";
		else
			cout << dst[i] << "\n";
	}
}