C++ / 프로그래머스 / 합승 택시 요금

문제

 

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

프로그래머스

 

 

 

문제풀이

 

처음에는 DFS로 풀어봤는데 결과가 좋지 않아서 질문글을 봤더니 다른 알고리즘으로 푸는 문제였다.

다익스트라 알고리즘으로 풀 수 있어서 따로 공부를 하고 풀었다.

해당 알고리즘을 모르고 풀 때와 알고 풀 때 푸는 시간이 확연히 차이 났다..

 

이 문제에서는 지점이 3개가 나온다 A, B, S.

따라서 A, B, S지점으로 부터 모든 지점까지의 최소 요금을 모두 알아야 한다.

A->x + B->x + x->S의 최솟값을 구해야 하기 때문에 다익스트라 알고리즘을 이용해 각각의 최소 요금을 구하고,

반복문을 통해 x가 1부터 N까지의 모든 요금중 최소 요금을 return하면 된다.

 

코드

#include <string>
#include <vector>
#include <queue>
#define MAX 2000000
using namespace std;

vector<vector<int>>fare;
int n1;

struct cmp {
    bool operator()(pair<int, int>a, pair<int, int>b) {
        return a.second > b.second;
    }
};

vector<int> Dijkstra(int start) {
    int idx(0), n_fare(0), next(0), node(0), o_fare(0);
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>pq;
    vector<int>fare_AB(n1 + 1, MAX);
    fare_AB[start] = 0;
    pq.push({ start, 0 });

    while (!pq.empty()) {
        node = pq.top().first;
        o_fare = pq.top().second;
        pq.pop();
        for (next = 1; next <= n1; ++next) {
            if (fare[node][next] != 0) {
                n_fare = fare[node][next];
                if (fare_AB[next] > o_fare + n_fare) {
                    fare_AB[next] = o_fare + n_fare;
                    pq.push({ next, fare_AB[next] });
                }
            }
        }
    }
    return fare_AB;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer(MAX), idx(0);
    n1 = n;
    fare = vector<vector<int>>(n + 1, vector<int>(n + 1, 0));
    vector<int>fare_A;
    vector<int>fare_B;
    vector<int>fare_S;

    for (idx = 0; idx < fares.size(); ++idx) {
        fare[fares[idx][0]][fares[idx][1]] = fares[idx][2];
        fare[fares[idx][1]][fares[idx][0]] = fares[idx][2];
    }

    fare_A = Dijkstra(a);
    fare_B = Dijkstra(b);
    fare_S = Dijkstra(s);

    for (idx = 1; idx <= n; ++idx) {
        answer = min(answer, fare_A[idx] + fare_B[idx] + fare_S[idx]);
    }

    return answer;
}