링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72413
문제 설명
A와 B는 택시를 타고 귀가하려고 합니다. 이때 A와 B는 가능한 택시요금이 적게나오는 루트로 합승하려고 합니다.
택시를 타고 갈 수 있는 n개의 지점 중 택시를 타는 s지점, A와 B의 집인 a, b지점, 각 지점간의 택시요금이 주어졌을 때, 최소 택시요금을 구하시오.
제한조건
* s, a, b 지점은 겹치지 않습니다. 또한 s지점에서 반드시 a, b 지점으로 갈 수 있는 경로만 주어집니다.
* n <= 200
아이디어
시작 지점 s에서 합승할 지점 k까지 간 후, k에서 각각 a, b지점으로 가는 최소 요금을 구하면 되니 각 지점 사이 최단거리를 미리 구해 놓고 위에 방법을 그대로 사용.
다른 방식으로는 시작지점에서 a, b를 도착지점으로하고 중간마다 경유를 할지 선택하는 방법은 더 귀찮을 것 같네요.
코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<vector<int>> table(201, vector<int>(201, 2e8));
int answer = 2e9;
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
for(auto fare : fares)
{
table[fare[0]][fare[1]] = fare[2];
table[fare[1]][fare[0]] = fare[2];
}
for(int i = 0; i <= n; i++) table[i][i] = 0;
for(int k = 0; k <= n; k++)
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
table[i][j] = min(table[i][j], table[i][k] + table[k][j]);
for(int i = 0; i <= n; i++)
answer = min(answer, (table[s][i] + table[i][a] + table[i][b]));
return answer;
}
아이디어와 동일하게 임의의 두 지점 i > j로 갈 때 최단거리를 벨만포드 알고리즘으로 구하고,
시작지점 s에서 합승 지점 i 까지 간 후 a, b로 가는 것에 최소 값을 체크.
'알고리즘' 카테고리의 다른 글
프로그래머스 - 여행경로(43164) (1) | 2023.08.29 |
---|---|
프로그래머스 - 표 병합(150366) (0) | 2023.08.29 |
프로그래머스 - 상담원 인원(214288) (0) | 2023.08.24 |
프로그래머스 - 보석 쇼핑(67258) (0) | 2023.07.07 |
프로그래머스 - 수식 최대화(67257) (0) | 2023.07.06 |