[프로그래머스] 합승 택시 요금 (C++)

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

코딩테스트 연습 - 합승 택시 요금

 

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

class Node{
    public:
    int id;
    int cost;
    Node(int id, int cost){
        this->id=id;
        this->cost=cost;
    }
};

struct cmp{
    bool operator()(const Node a, const Node b){
        return a.cost > b.cost;
    }
};

vector<vector<Node> > adjList(201);
int distS[201];

int dijkstra(int start, int a, int b){
    int dist[201];
    priority_queue<Node, vector<Node>, cmp> pq;
    for (int i=0; i<201; i++){
        dist[i]=MAX;
    }
    dist[start]=0;
    pq.push(Node(start, 0));
    while (!pq.empty()){
        Node now=pq.top();
        pq.pop();
        if (now.cost > dist[now.id]){
            continue;
        }
        int len=adjList[now.id].size();
        for (int i=0; i<len; i++){
            Node next=adjList[now.id][i];
            if (now.cost+next.cost < dist[next.id]){
                dist[next.id]=now.cost+next.cost;
                pq.push(Node(next.id, dist[next.id]));
            }
        }
    }
    return dist[a]+dist[b];
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = MAX;
    priority_queue<Node, vector<Node>, cmp> pq;
    for (int i=0; i<fares.size(); i++){
        int c=fares[i][0];
        int d=fares[i][1];
        int f=fares[i][2];
        adjList[c].push_back(Node(d,f));
        adjList[d].push_back(Node(c,f));
    }
    for (int i=0; i<201; i++){
        distS[i]=MAX;
    }
    distS[s]=0;
    pq.push(Node(s, 0));
    while (!pq.empty()){
        Node now=pq.top();
        pq.pop();
        if (now.cost > distS[now.id]){
            continue;
        }
        int len=adjList[now.id].size();
        for (int i=0; i<len; i++){
            Node next=adjList[now.id][i];
            if (now.cost+next.cost < distS[next.id]){
                distS[next.id]=now.cost+next.cost;
                pq.push(Node(next.id, distS[next.id]));
            }
        }
    }
    for (int i=1; i<=n; i++){
        if (distS[i]==MAX){     //S와 직접 연결된 vertex가 아니면
            continue;
        }
        if (i==s){
            answer=min(answer, distS[a]+distS[b]);
        }
        else{
            answer=min(distS[i]+dijkstra(i,a,b), answer);
        } 
    }  
    return answer;
}

주의!!!

엄청 길고 더럽게 괜히 어렵게 풀었다

 

다익스트라를 사용해서 풀었다.

나의 풀이방법은 이렇다.

시작점 S부터 다른 지점까지의 최단거리를 구한다. 여기서 구한 다익스트라 dist는 합승 시작점(S) - 합승 종료점까지의 최단거리이다.

1부터 n까지 돌면서 다익스트라를 수행해, 각 i번째를 합승 종료점으로 삼는다.  

또 그 i번째를 출발지로 설정해 다익스트라를 돌려서 i번째-a지점, i번째-b 지점 까지의 최단거리를 구하고, 이를 더해 최소값을 얻는다.

 

근데.. 이렇게 여러번 다익스트라를 돌릴 필요 없이 (시간복잡도는 이 경우 O(N*E*logV) 이다, E가 N^2 형태로 나오니까 대략 O(N^3*logN) .. 플로이드 워셜 쓰면 O(N^3).. 다익스트라를 써서 복잡함과 미묘한 시간복잡도의 증가를 얻었다 ^^)

플로이드 워셜을 이용하면 된다. 

플로이드 워셜은 각 지점간의 최단거리를 구하는 알고리즘이고, 

합승 종료점까지 min(floyd[합승시작][합승종료]+floyd[합승종료][a]+floyd[합승종료][b]) 이렇게 구해주면 된다....

괜히 복잡해졌다. 아이디어는 사실 유사한데, 그걸 구현해내는 방식이 플로이드냐/다익스트라냐에 따라 복잡성이 갈렸던것 같다(그리고 코드 길이도 ....)

 

여기서 포인트는

 

(합승 시작점-합승 종료점-각 a,b 까지의 거리) 가 min 이 되도록 구하는 것이다.

플로이드 워셜은 모든 지점 간 최단거리를 구해주는 알고리즘이므로, 합승 종료점을 1부터 n까지 돌려가면서 가장 최소값을 갖는 애를 답으로 선정하면 된다.