문제 푼 날짜 : 2021-08-05

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72413

접근 및 풀이

이전에 Floyd-Warshall 알고리즘을 이용하여 문제를 풀어봤는데, 이번엔 Dijkstra 알고리즘으로 풀어보았다.
일반적인 Dijkstra 알고리즘을 통해 주어진 s, a, b에서 출발하여 모든 노드에 도달하는 최단경로를 구해주었다.
그리고 출발지점(s)에서 합승하여 택시를 이동하는 임의의 노드(x)까지 거리와 도착지(a, b) 각각에서 거꾸로 출발하여 노드(x)까지의 거리를 합했을 때 최단거리를 구해주었다.

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

#define INF 987654321

vector<pair<int, int>> map[201];

vector<int> dijkstra(int start) {
    vector<int> distance(201, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    distance[start] = 0;
    pq.push(make_pair(0, start));
    
    while (!pq.empty()) {
        int cost = pq.top().first;
        int now = pq.top().second;
        pq.pop();
        
        if (distance[now] < cost) {
            continue;
        }
        for (int i = 0; i < map[now].size(); i++) {
            int next = map[now][i].first;
            int nCost = cost + map[now][i].second;
            
            if (distance[next] > nCost) {
                distance[next] = nCost;
                pq.push(make_pair(nCost, next));
            }
        }
    }
    return distance;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    
    for (auto f : fares) {
        map[f[0]].push_back(make_pair(f[1], f[2]));
        map[f[1]].push_back(make_pair(f[0], f[2]));
    }
    vector<int> from_s = dijkstra(s); // s에서 출발한 최단거리
    vector<int> from_a = dijkstra(a); // a에서 출발한 최단거리
    vector<int> from_b = dijkstra(b); // b에서 출발한 최단거리
    
    answer = from_s[a] + from_s[b];
    for (int i = 1; i <= n; i++) {
        if (i == s) {
            continue;
        }
        if (from_s[i] == INF || from_a[i] == INF || from_b[i] == INF) {
            continue;
        }
        answer = min(answer, from_s[i] + from_a[i] + from_b[i]);
    }
    return answer;
}

결과

피드백

같은 문제를 다르게 풀어보는 시도를 많이 해봐야겠다.