2021 KAKAO Blind - 4. 합승 택시 요금

목차

개요
설명
코드

개요

정확성과 효율성을 동시에 체크하는 문제입니다.

 

무지와 어피치는 같이 택시를 합승해 어느 지점까지 이동한 뒤에, 각자 개인 택시를 이용하여 집으로 귀가합니다. 시점은 동일하고 중간 경유지까지 함께 간 뒤에 헤어져 각자의 목적지로 향하는 방식입니다.

 

따라서 직관적으로 (출발지 → 경유지), (경유지 → 무지의 집), (경유지 → 어피치의 집) 의 합이 최소가 되도록 하는 "경유지"를 구한 뒤, 비용을 계산하면 됩니다.

 

$$Answer =min( d[S,\ l]\ +\ d[l, \ A]\ +\ d[l,\ B])$$

 

여기서 $l$은 경유지 입니다.

 

플로이드 워셜을 사용하면 모든 시점 → 종점의 비용을 계산할 수 있습니다. 그러나 시간복잡도는 $O(V^3)$으로 상당한 시간복잡도를 지니고 있습니다. 따라서 시간 초과의 우려가 있습니다.

 

우리에게 $O(ElogV)$만에 특정 시점과 모든 점 사이의 최단거리를 계산할 수 있는 다익스트라 알고리즘이 있습니다. 이 다익스트라 알고리즘을 사용해서

• S로부터 모든 정점까지의 최단 거리
• A로부터 모든 정점까지의 최단 거리
• B로부터 모든 정점까지의 최단 거리

를 구한 뒤에, $d[S,\ l]\ +\ d[l, \ A]\ +\ d[l,\ B]$ 가 최소가 되는 정점 $l$을 구하고, 값을 반환하면 됩니다.

 

 

설명

위는 카카오 예제 문제입니다. S로부터 최단거리를 다익스트라를 통해 구하면 다음과 같습니다.

마찬가지로 A로부터 각 정점까지의 최단 거리를 구하면 다음과 같습니다.

B로부터 각 정점까지의 최단 거리를 구하면 다음과 같습니다.

이제 각 노드에 대해서 $d[S,\ l]\ +\ d[l, \ A]\ +\ d[l,\ B]$ 를 계산하면 다음과 같습니다.

여기서 82가 최소이므로, 정답은 82입니다.

 

 

코드

※주의할 점

문제에서 "모든 정점이 연결되어 있다"라는 보장은 없습니다. 따라서 초기 값을 잘 초기화 해서, 닿을 수 없는 노드는 어떤 곳이 있는지 구분해야 합니다. (단, 정답은 항상 존재한다고 문제에서 제시하였습니다.)

#include <string>
#include <vector>
#include <queue>
#define IMAX 2147483647
using namespace std;
class Point{
    public:
    int node;
    int cost;
    Point (int node_, int cost_): node(node_), cost(cost_){};
    bool operator<(const Point& b) const{ 
        return this->cost < b.cost;
    }
};
vector<pair<int, int>> graph[200];
priority_queue<Point> pq;

int from_s[200];
int from_a[200];
int from_b[200];
int dijkstra(int src, int* from, int n){
    int cur = src;
    int cur_cost = 0;
    pq.push(Point(cur, 0));
    for(int i=0; i<n; i++){
        from[i] = IMAX;
    }
    from[src] = 0;
    while(!pq.empty()){
        cur = pq.top().node;
        cur_cost = pq.top().cost;
        pq.pop();
        for(auto itr = graph[cur].begin(); itr != graph[cur].end(); itr++){
            int next = itr->first;
            int next_cost = itr->second + cur_cost;
            if(from[next] > next_cost){
                from[next] = next_cost;
                pq.push(Point(next, next_cost));
            }
        }
    }
    return 0;
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    for(auto itr = fares.begin(); itr != fares.end(); itr++){
        graph[(*itr)[0]-1].push_back(std::make_pair((*itr)[1]-1,(*itr)[2]));
        graph[(*itr)[1]-1].push_back(std::make_pair((*itr)[0]-1,(*itr)[2]));
    }
    dijkstra(s-1, from_s, n);
    dijkstra(a-1, from_a, n);
    dijkstra(b-1, from_b, n);

    answer = IMAX;
    for(int i=0; i<n; i++){
        if(from_s[i] == IMAX || from_a[i] == IMAX || from_b[i] == IMAX) continue;
        int val = 1LL * from_s[i] + 1LL * from_a[i] + 1LL * from_b[i];
        if(answer > val)
            answer = val;
    }

    return answer;
}