프로그래머스 Level 3 합승택시요금

합승택시요금 (프로그래머스 Level 3)

https://school.programmers.co.kr/learn/courses/30/lessons/72413

그래프 문제이며, 최단 경로와 관련된 문제이다
플로이드-워셜을 적용하여 풀 수 있겠다 싶었다
(총 자료의 개수가 약 200개 이하이므로, O(n^2)인 플로이드-워셜을 사용해도 될거라 판단하였다)

다만, 처음에는 s -> a -> b 와 s -> b -> a 중 작은 것을 고르면 된다고 생각하였으나
문제를 자세히 읽어보니 ‘s -> 공유 지점’, 이후
‘공유지점 -> a’, ‘공유지점 -> b’ 인 것을 확인할 수 있었다

플로이드-워셜로 만든 2차원 배열을 탐색하며,
각각의 ‘점’ 중 무엇을 공유 지점으로 삼았을 때
가장 적은 값이 나오는지 탐색하는 방식으로 풀 수 있었다

Code

#include <string>
#include <vector>
#include <unordered_map>
#include<limits.h>

using namespace std;

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {

	// input 값 정리하기
	unordered_map<int, vector<pair<int, int>>> edges;
	for (const auto& fare : fares)
	{
		int begin = fare[0] - 1;
		int to = fare[1] - 1;
		int cost = fare[2];

		if (edges.find(begin) == edges.end())
		{
			edges[begin] = vector<pair<int, int>>();
		}

		edges[begin].push_back(make_pair(to, cost));

		if (edges.find(to) == edges.end())
		{
			edges[to] = vector<pair<int, int>>();
		}

		edges[to].push_back(make_pair(begin, cost));
	}

	// 약간의 매직 넘버 스럽지만
	// limit를 너무 크게 잡으면 overflow
	// 너무 낮게 잡으면 오답이 나온다 (limit보다 더 큰값이 생성)
	const int limit = INT_MAX / 10;
	vector<vector<int>> fw(n, vector<int>(n, limit));

	// 플로이드 - 워셜
	{
		for (int i = 0; i < n; i++)
		{
			fw[i][i] = 0;
		}

		for (const auto& edge : edges)
		{
			int s = edge.first;
			const auto& info = edge.second;
			for (const auto& i : info)
			{
				int t = i.first;
				int cost = i.second;
				fw[s][t] = cost;
			}
		}

		for (int k = 0; k < n; k++)
		{
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					fw[i][j] = min(fw[i][j], fw[i][k] + fw[k][j]);
				}
			}
		}
	}

	// 특정한 최단 경로 문제
	int answer = limit;

	for (int i = 0; i < n; i++)
	{
		// 'i'가 A와 B가 나뉘는 '중간' 지점
		// 플로이드-워셜로 구한 i -> s , i -> a, i -> b의
		// 합이 가장 적은 것이 정답
		int totalCost = fw[s - 1][i] + fw[i][a - 1] + fw[i][b - 1];
		answer = min(answer, totalCost);
	}

	return answer;
}