백준[1916]_최소비용_구하기 C++ 풀이

Nilo의 개발 일지·2021년 7월 11일
0

알고리즘

목록 보기
7/29
post-custom-banner

백준[1916] 최소비용 구하기

아이디어

  • 다익스트라 알고리즘을 사용할 줄 안다
  • 우선순위 큐를 사용할 줄 안다

접근 방식

  1. 시작 노드, 도착 노드, 비용을 저장해준다
  2. 우선순위 큐를 이용하여 다익스트라 알고리즘을 실행한다
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <math.h>
#include <queue>

#define MAX 987654321

using namespace std;

int main()
{
	int town_cnt, bus_cnt; scanf("%d %d", &town_cnt, &bus_cnt);

	//pair(도착지점, 비용)
	vector<pair<int,int>> town_and_go[1001];

	for (int i = 0; i < bus_cnt; i++)
	{
		int start_town, stop_town, bus_cost; scanf("%d %d %d", &start_town, &stop_town, &bus_cost);
		town_and_go[start_town].push_back({ stop_town,bus_cost });
	}

	int start_town, stop_town;
	scanf("%d %d", &start_town, &stop_town);

	int dist[1001]; //각 노드에서의 최단 거리
	fill(dist, dist + 1001, MAX);
	dist[start_town] = 0; //시작 도시는 0으로 초기화

	//pair(노드 번호, 노드 까지의 최단 cost)
	priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

	pq.push({ start_town,0 });

	while (!pq.empty())
	{
		int now_town_num = pq.top().first;
		int now_cost = pq.top().second; //최소를 top으로 해야하기에 음수를 넣어줌!
		pq.pop();

		if (dist[now_town_num] < now_cost) continue;

		for (int i = 0; i < town_and_go[now_town_num].size(); i++)
		{
			int next_town_num = town_and_go[now_town_num][i].first;
			int next_cost = town_and_go[now_town_num][i].second;

			//만약 현재cost + 간선 비중 < 다음 갈 최단비용 이면 갱신 후 큐에 넣어줌
			if (now_cost + next_cost < dist[next_town_num])
			{
				dist[next_town_num] = now_cost + next_cost;
				pq.push({ next_town_num,dist[next_town_num] });
			}
		}
	}

	printf("%d\n", dist[stop_town]);

	return 0;
}

평가

다익스트라 알고리즘을 알고 있으면 풀기 쉬운 문제.
하지만 저는

if (dist[now_town_num] < now_cost) continue;

이 코드를 넣는 것을 몰라, 시간초과가 계속 발생했습니다.
위 코드는 같은 번호의 노드가 priority_queue에 여러개 들어갈 수도 있는데, 과거에 pq에 넣어준 최단거리가 최근 갱신한 최단거리보다 클 경우에는 굳이 다익스트라를 할 필요 없이 넘어가주면 된다는 의미를 가집니다.

  • 배울 것 : 다익스트라에서 priority queue에 최단거리가 갱신되는 것을 확인하자
profile
프론트와 알고리즘 저장소
post-custom-banner

0개의 댓글