[Programmers] 합승 택시 요금

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

저는 다익스트라 알고리즘을 통해 푼 문제인데 정석 풀이를 보면 플로이드-와샬 알고리즘으로 푼 문제였습니다.

일단 제가 푼 코드를 기반으로 설명을 진행하고 추후에 플로이드-와샬 코드도 올리도록 하겠습니다.

 

알고리즘은 아래와 같습니다.

1. 시작점 s를 기준으로 다익스트라 알고리즘을 진행하고 그 결과를 sDistance에 저장합니다.

2. [1, n] 지점을 순회하며 각 지점을 기준으로 다익스트라 알고리즘을 진행하고 결과를 vDistance에 저장합니다.

2.1 현재 기준이 되는 지점을 v라고 했을 때 s -> v로 가는 비용, v -> a로 가는 비용, v -> b로 가능 비용의 합산이 answer보다 작을 경우 answer를 업데이트해줍니다.

3. answer를 반환합니다.

	#include <string>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <climits>
	using namespace std;
	const int MAX = 200 + 1;
	const int INF = 2e6 + 2e3;
	vector<pair<int, int>> edges[MAX];
	vector<int> dijkstra(int start)
	{
	vector<int> distance(MAX, INF);
	distance[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	while (!pq.empty())
	{
	int cost = -pq.top().first;
	int curVertex = pq.top().second;
	pq.pop();
	if (distance[curVertex] < cost)
	{
	continue;
	}
	for (pair<int, int> vertex : edges[curVertex])
	{
	int neighbor = vertex.first;
	int neighborDistance = cost + vertex.second;
	if (distance[neighbor] > neighborDistance)
	{
	distance[neighbor] = neighborDistance;
	pq.push({ -neighborDistance, neighbor });
	}
	}
	}
	return distance;
	}
	int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
	for (vector<int> fare : fares)
	{
	int u = fare[0];
	int v = fare[1];
	int cost = fare[2];
	edges[u].push_back({ v, cost });
	edges[v].push_back({ u, cost });
	}
	vector<int> sDistance = dijkstra(s);
	int answer = INT_MAX;
	for (int vertex = 1; vertex <= n; vertex++)
	{
	vector<int> vDistance = dijkstra(vertex);
	answer = min(answer, vDistance[a] + vDistance[b] + sDistance[vertex]);
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~