[백준] 5972번 : 택배 배송

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 최단 거리를 구하는 문제로, 다익스트라 알고리즘을 사용하여 풀이했다.

1) 헛간 개수 n과 길의 개수 m을 입력 받아 저장한다.
이 때, 헛간 개수 == 노드 개수 / 길의 개수 == 간선 개수 라고 볼 수 있다.

2) 2차원 벡터 graph를 선언하고 n + 1 크기로 초기화 한다. 그리고 m개의 길에 대한 정보 pair(헛간 번호, 소의 마리수(가중치))를 입력 받아 graph에 저장한다. 이 때, 헛간끼리 이어진 길은 양방향으로 이동 가능하므로 간선 저장 시 양방향으로 이어준다.

3) 시작점인 1에서 각 헛간까지 최단 거리를 저장하는 배열 dp를 선언하고, dp의 모든 값을 무한대로 초기화한다.

4) 다익스트라 알고리즘을 실행하여 시작점에서부터 각 위치까지의 최단 거리를 구한다.

• 최소힙으로 구현하기 위해 우선순위 큐 pq를 선언하고, 오름차순으로 정렬되도록 한다.
  • pq에는 노드 정보 (해당 노드까지 최소 거리, 노드 번호)가 저장된다.
• pq에 (0, 시작 위치)를 삽입한다.
• dp[start](시작점에서부터 시작점까지의 최단 거리)를 0으로 초기화한다.
• pq가 빌 때까지 아래 과정을 반복한다.
  • pq에 저장되어 있는 노드 중 가중치가 가장 작은 노드에 대한 정보를 꺼낸다.
    • dist : 현재 노드까지의 거리
    • cur : 현재 노드의 번호
  • 만약 dp[cur] < dist라면 이미 최단 거리가 구해진 노드이므로 무시한다.
  • 위 경우가 아니라면 해당 노드의 인접 노드들에 대해 아래 과정을 반복한다.
    • cost : 현재 노드까지의 거리 + 현재 노드 ~ 인접 노드까지의 거리
    • 만약 cost가 저장되어있던 인접 노드의 dp보다 작다면 (cost < dp[인접 노드])
      • 인접 노드의 dp를 cost로 갱신한다.
      • 갱신된 인접 노드 정보 (인접 노드까지 최소 거리, 노드 번호)를 pq에 삽입한다.

4) 위 과정이 끝나면 dp에는 시작점부터 다른 노드까지의 최소 거리들이 저장된다.
이 때, 헛간 n까지의 최단 거리를 알고 싶은 것이기 때문에 dp[n]을 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

int n, m;
vector<vector<pii>> graph;
int dp[50001];
const long long INF = 1e9;

void dijkstra(int start)
{
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push(pii(0, start));
	dp[start] = 0;

	while (!pq.empty())
	{
		int dist = pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (dp[cur] < dist) continue;
		for (int i = 0; i < graph[cur].size(); i++)
		{
			int cost = dist + graph[cur][i].second;
			if (cost < dp[graph[cur][i].first])
			{
				dp[graph[cur][i].first] = cost;
				pq.push(pii(cost, graph[cur][i].first));
			}
		}
	}
}

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

	cin >> n >> m;
	graph.resize(n + 1);

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		// 양방향 간선이므로 양쪽 노드에 모두 추가
		graph[a].push_back(pii(b, c));
		graph[b].push_back(pii(a, c));
	}

	fill(dp, dp + n + 1, INF);
	dijkstra(1);

	cout << dp[n];
}