[백준] 1446번 : 지름길

🔗 문제 링크

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

✍️ 문제 풀이

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

1) 지름길의 개수 m과 고속도로의 길이 n을 입력 받아 저장한다.
=> 여기서 고속도로 길이는 노드의 개수와 같다.

2) 2차원 벡터 graph를 선언하고 n + 1 크기로 초기화 한다. 그리고 m개의 지름길에 대한 정보 pair(상대 노드 번호, 가중치)를 입력 받아 graph에 저장한다. 또한 0 ~ n까지 각 위치에서 +1 위치로 가중치 1의 간선을 연결한다.

3) 시작점에서 각 위치까지 최단 거리를 저장하는 배열 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에는 시작점부터 다른 노드까지의 최소 거리들이 저장된다.
이 때, 0 ~ n이 현재 위치라고 가정할 때, 현재 위치까지의 최소 거리 + (목적지 - 현재 위치)를 전부 비교하여 가장 작은 값을 출력한다.

🖥️ 풀이 코드

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

int n, m;
vector<vector<pii>> graph;	// 0 ~ n까지 각 위치와 연결된 다른 위치들의 pii(인덱스, 거리)를 저장 
int dp[10001];				
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 >> m >> n;
	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));
	}

	// 0 ~ n까지 각 위치에서 +1 위치로 간선 연결 (길이는 1)
	for (int i = 0; i <= n; i++)
		graph[i].push_back(pii(i + 1, 1));

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

	// 0 ~ n이 현재 위치일 때 -> 현재 위치까지의 최소 거리 + (목적지 - 현재 위치)를 전부 비교하여 가장 작은 값 찾기
	int minDist = INF;
	for (int i = 0; i <= n; i++)
	{
		int curDist = dp[i] + (n - i);	
		if (curDist < minDist)
			minDist = curDist;
	}
	cout << minDist;
}