1916. 최소비용 구하기

백준 1916번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

1916번: 최소비용 구하기

풀이

아이디어

무난한 다익스트라 문제라고 생각했는데 한번은 틀리고 한번은 시간초과가 났다. 같은 실수를 반복하지 않기 위해서 간단히 기록해둔다.

첫번째 틀린 이유는 방향이 없는 그래프라고 생각했기 때문이었다. 문제에서 방향에 대한 언급을 직접적으로 하진 않았지만 버스의 정보를 줄 때 “출발 도시”와 “도착 도시”의 정보를 줬기 때문에 방향이 있는 것으로 해석하는게 자연스러웠다.

두번째 시간 초과의 이유는 무작정 큐가 빌 때 까지 계속해서 업데이트를 해 줬기 때문이다. queue에서 뽑아낸 거리가 기존에 저장해두었던 최단거리 배열의 값보다 “큰” 경우에는 아무리 더해도 최단거리 배열의 업데이트가 일어나지 않을 것이기 때문에 굳이 업데이트 해 줄 필요가 없었다.

운이 좋게 예전에 풀었던 다익스트라 문제에서는 시간 초과 문제는 발생하지 않았던 것 같은데 (아닐수도… 내 기억력의 문제일수도…) 잘 기억해둬야겠다.

코드

// 백준 1916 최소비용 구하기
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#define INF 10000000000;
using namespace std;

int n, m;
int src, dest;
long shortest_dist[1001];
vector<pair<int, long> >connected[1001];

void input()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	int s, d;
	long w;
	for (int i = 0; i < m; i++)
	{
		cin >> s >> d >> w;
		connected[s].push_back(make_pair(d, w));
	}
	for(int i = 1; i <= n; i++)
		shortest_dist[i] = INF;
	cin >> src >> dest;
}

void dijkstra()
{
	priority_queue<pair<long, int>, vector<pair<long, int> >, greater<pair<long, int> > > pq; // first : dist, second : point
	long curr_dist, temp_dist;
	int curr_point, temp_point;
	pq.push(make_pair(0, src));
	shortest_dist[src] = 0;
	while (!pq.empty())
	{
		curr_dist = pq.top().first;
		curr_point = pq.top().second;
		pq.pop();
		if (shortest_dist[curr_point] < curr_dist)
			continue;
		for (int i = 0; i < connected[curr_point].size(); i++)
		{
			temp_point = connected[curr_point][i].first;
			temp_dist = connected[curr_point][i].second;
			if (shortest_dist[temp_point] > curr_dist + temp_dist)
			{
				shortest_dist[temp_point] = curr_dist + temp_dist;
				pq.push(make_pair(shortest_dist[temp_point], temp_point));
			}
		}
	}

}

int main()
{
	input();
	dijkstra();
	cout << shortest_dist[dest];
	return (0);
}

시간 / 공간 복잡도

• 시간 복잡도: 우선순위 큐를 사용한 다익스트라로 O((V + E) log V). V는 최대 1,000, E는 최대 100,000이므로 충분히 통과 가능하다.
• 공간 복잡도: 인접 리스트와 최단거리 배열로 O(V + E).