[Baekjoon] 1916번: 최소비용 구하기

 

 

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

1916번: 최소비용 구하기

 

---

 

문제 해결 과정

착안

음의 가중치 간선이 존재하지 않으며 방향이 있는 그래프에 대한 최단 경로 탐색을 요구하는 문제이므로, 최단 경로 탐색 알고리즘 중 하나인 데이크스트라 알고리즘(Dijkstra's algorithm)을 사용하여 문제를 해결하고자 했다.

 

구현

데이크스트라 알고리즘을 정상적으로 구현했음에도 불구하고 시간 초과가 발생하여 한참 고민하다가 질문 게시판에서 힌트를 참고하여 문제를 해결하였다.

 

문제에서 언급하지는 않았으나, 동일한 시점과 종점을 가지면서 가중치만 다른 간선이 대량으로 존재하는 경우에 대한 테스트 케이스가 있어 이 부분에서 시간 초과가 발생하는 것 같다. 따라서, 이를 해결하기 위해 간선 데이터를 모두 입력받은 다음 정점 별로 간선들을 가중치에 대한 오름차순으로 정렬한 결과, 문제를 해결할 수 있었다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

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

using namespace std;

struct Edge
{
	int From;
	int Dest;
	int Cost;
};

struct City
{
	int CostSum = 2147483647;
	bool Visited = false;
	vector<Edge> Edges;
};

City Cities[1000];

struct cmp
{
	bool operator()(const int& idx1, const int& idx2) const
	{
		return Cities[idx1].CostSum > Cities[idx2].CostSum;
	}
};

void Dijkstra(int start, int end)
{
	Cities[start - 1].CostSum = 0;

	priority_queue<int, vector<int>, cmp> pq;
	pq.push(start - 1);
	while (!pq.empty())
	{
		int index = pq.top();
		pq.pop();

		City& current = Cities[index];
		current.Visited = true;

		if (index == end - 1)
		{
			cout << current.CostSum << "\n";
			return;
		}

		for (Edge e : current.Edges)
		{
			if (!Cities[e.Dest].Visited &&
				Cities[e.Dest].CostSum > current.CostSum + e.Cost)
			{
				Cities[e.Dest].CostSum = current.CostSum + e.Cost;
				pq.push(e.Dest);
			}
		}
	}
}

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

	int N, M;
	cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		int from, dest, cost;
		cin >> from >> dest >> cost;
		Cities[from - 1].Edges.push_back(Edge{ from - 1, dest - 1, cost });
	}

	for (City& city : Cities)
		sort(city.Edges.begin(), city.Edges.end(), [](const Edge& A, const Edge& B) { return A.Cost < B.Cost; });

	int Start, End;
	cin >> Start >> End;
	Dijkstra(Start, End);
	return 0;
}

 

실행 결과