합승 택시 요금
프로그래머스 합승 택시 요금 풀이
문제설명
밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지
는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. “무지”는 자신이 택시를 이용할 때 동료인 어피치
역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. “무지”는 “어피치”와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 “어피치”에게 합승을 제안해 보려고 합니다.
문제는 무지와 어피치가 중간지점(시작부터 같이 안탈 수 있음)까지 같이 탑승하고, 중간지점에서 각각의 집까지 택시를 탑승한뒤 무지와 어피치의 택시요금이 얼마인지 계산한다. 이때 택시요금의 최솟값을 찾는 문제이다.
제한사항
- 노드의 개수 ≤ 200
해결과정
노드의 개수가 200이므로, $O(N^3)$의 플로이드 와샬 알고리즘을 사용해도 $10^7$을 넘지않는다.
플로이드 와샬 알고리즘을 사용하여, 모든 노드에서의 최단거리를 구한다. 이후 모든 중간지점에 대한 택시요금을 계산하고, 최솟값을 찾는다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define INF 987654321
using namespace std;
// start -> 중간지점
// 중간지점 -> A의 지점
// 중간지점 -> B의 지점
// 3개의 합
int dst[201][201];
void Init(){
for(int i = 0; i<=200;i++)
for(int j = 0; j<=200; j++){
dst[i][j] = INF;
if(i == j) dst[i][j] = 0;
}
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
Init();
for(const vector<int>& v : fares){
dst[v[0]][v[1]] = dst[v[1]][v[0]] = v[2];
}
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j<=n; j++){
if(dst[i][k] == INF || dst[k][j] == INF || i == j) continue;
if(dst[i][j] > dst[i][k] + dst[k][j]) dst[i][j] = dst[i][k] + dst[k][j];
}
int ans = INF;
for(int mid= 1; mid<=n;mid++){
if(dst[s][mid] == INF || dst[mid][a] == INF || dst[mid][b] == INF) continue;
ans = min(ans, dst[s][mid] + dst[mid][a] + dst[mid][b]);
}
return ans;
}
This post is licensed under CC BY 4.0 by the author.