A와 B가 집까지 가는 데 걸리는 최소 택시 요금을 구하는 문제이다.
중간까지 같이 가다가 중간지점에서 둘이 따로 택시를 타도 된다.
문제 해결 전략
시작점과 목표지점 두개가 주어진다.
시작점부터 중간점까지의 요금과 중간점에서 각 점까지의 요금의 합이 최소가 되는 점을 찾으면 된다.
위의 요금을 구하기 위해서는 모든 점들 사이의 요금 최솟값을 구하면 된다.
그 후 모든 점에 대하여 시작점 부터 그점, 그점부터 각 점까지의 거리의 합 중 최소가 되는 값을 구하면 된다.
우선 모든 점들 사이의 요금 최솟값을 구하기 위해 플로이드 워셜 알고리즘을 사용하였다.
플로이드 워셜
모든 점들 사이의 거리를 굉장히 큰 수로 하고 자기 자신까지의 거리일 때만 0으로 해 준다.
그리고 중간점 k에 대하여 i에서 k까지의 요금 + k에서 j까지의 요금와 i에서 j까지의 요금을 비교하여 더 작은 값을 i에서 j까지의 요금에 저장해 준다.
k를 모든 점에 대하여 실행해 준다.
요금 구하기
앞서 구한 모든 점들 간의 최소 요금을 가지고 반복문을 통해 모든 점에 대하여 확인해 준다.
코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int taxi[201][201];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
int answer = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i == j)
taxi[i][j] = 0;
else
taxi[i][j] = 12345678;
}
}
for(int i=0;i<fares.size();i++){
int aa = fares[i][0];
int bb = fares[i][1];
int cc = fares[i][2];
taxi[aa][bb] = cc;
taxi[bb][aa] = cc;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int tmp = taxi[i][k] + taxi[k][j];
taxi[i][j] = min(taxi[i][j], tmp);
taxi[j][i] = min(taxi[i][j], tmp);
}
}
}
int mi = taxi[s][a] + taxi[s][b];
for(int i=1;i<=n;i++){
if(s == i)
continue;
mi = min(mi, taxi[s][i] + taxi[i][a] + taxi[i][b]);
}
answer = mi;
return answer;
}
출처 : 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/72413