[프로그래머스] 2021 KAKAO BLIND RECRUITMENT : 합승 택시 요금 (C++)

문제 링크 : 합승 택시 요금

[문제 접근]

기본적으로 최단경로 문제여서 최단경로 알고리즘을 떠올리며 접근했다.
문제를 해결하기 위해서는 어떤 정점까지 합승하고 이후 부터는 각자 귀가한다고 했으므로 적절한 정점을 찾는 것이 포인트인 것 같다.

아래 설명에서 합승점은 합승이 끝나는 정점이라고 가정한다.

• 적절한 합승점을 찾기 위해서 전체 정점을 탐색한다.
• i번째까지 합승한다고 가정하면 s->i의 최단경로, i->a의 최단경로, i->b의 최단경로를 합한다.
• 이 때, 최단경로를 구하면서 구하고자 하는 정점에 도달했다면 더 이상 탐색하지 않고 다익스트라 알고리즘을 빠져나오면 시간초과를 피할 수 있다.
  • 우선순위 큐를 사용하기 때문에 원하는 정점에 도달했다면 그 경로가 무조건 최단경로인 것을 이용
• 모든 정점을 돌면서 answer를 업데이트해준다.

나는 다익스트라가 익숙해서 다익스트라로 풀었는데 하나의 정점을 거쳐간다는 흐름이고 모든 정점 사이의 최단거리를 구해야하므로 플로이드 워샬을 사용하는 것이 더 적절한 풀이법인 것 같다.

[소스 코드]

다익스트라

#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> p;
vector<p> arr[201];
int dist[201];

int Dijkstra(int start, int end) {
    memset(dist, -1, sizeof(dist));
    dist[start] = 0;
    priority_queue<p, vector<p>, greater<p>> pq;
    pq.push(p(0, start));
    
    while(!pq.empty()) {
        int cur = pq.top().second;
        pq.pop();
        
        if(cur==end) break; // 시간초과 피하는 포인트
        
        for(int i=0 ; i<arr[cur].size() ; i++) {
            int next = arr[cur][i].first;
            if(dist[next]==-1 || dist[next]>dist[cur]+arr[cur][i].second) {
                dist[next] = dist[cur]+arr[cur][i].second;
                pq.push(p(dist[next], next));
            }
        }
    }
    
    return dist[end];
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = -1;
    for(int i=0 ; i<fares.size() ; i++) {
        arr[fares[i][0]].push_back(p(fares[i][1], fares[i][2]));
        arr[fares[i][1]].push_back(p(fares[i][0], fares[i][2]));
    }
    
    for(int i=1 ; i<=n ; i++) {
        int sTonode = Dijkstra(s, i);
        int nodeToa = Dijkstra(i, a);
        int nodeTob = Dijkstra(i, b);
        if(sTonode==-1 || nodeToa==-1 || nodeTob==-1) {
            continue;
        } else {
            int num = sTonode+nodeToa+nodeTob;
            if(answer==-1 || answer>num) answer=num;
        }
    }
    
    return answer;
}

플로이드 워샬

#include <string>
#include <vector>
using namespace std;

int dist[201][201];
const int maxnum = 5000000;
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer=maxnum;
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            dist[i][j] = (i == j ? 0 : maxnum);
        }
    }
    
    for(vector<int> fare : fares) {
        int x = fare[0], y = fare[1], z = fare[2];
        dist[x][y] = dist[y][x] = z;
    }

    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
        
    for(int i=1; i<=n; i++) {
        answer = min(answer, dist[s][i] + dist[i][a] + dist[i][b]);
    }

    return answer;
}