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

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

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

카카오 기출 문제

 

다익스트라를 통해 시작점에서부터 합승 거리의 최소 비용을 구하고, 다시 한번 다익스트라를 사용해 합승이 끝난 지점에서 a도착점과 b도착점으로의 최소 비용을 구해 이를 더한 값이 최소인 것을 찾으면 되는 문제라고 생각했습니다. 근데 효율성검사 7번, 8번에서 계속 TLE이 발생했고 아직 원인이 무엇인지 파악하지 못했습니다.

 

따라서 다른 풀이 방법으로 플로이드 와샬을 사용했습니다.

 

/* 플로이드 와샬 */

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

int dist[201][201];

void F(int n) {
    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]);
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 2147000000;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i != j) dist[i][j] = 4000000;
        }
    }
    
    for(auto f : fares) {
        dist[f[0]][f[1]] = f[2];
        dist[f[1]][f[0]] = f[2];
    }
    
    F(n);
    
    for(int i = 1; i <= n; i++) {
        int sum = dist[s][i] + dist[i][a] + dist[i][b];
        answer = min(answer, sum);
    }
    
    return answer;
}

 

/* 다익스트라 (미해결) */

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

int dist[201], tmp[201];
vector<pair<int, int> > graph[201];

void D(int node) {
    priority_queue<pair<int, int >, vector<pair<int, int > >, greater<pair<int, int > > > pq;
    pq.push({ 0, node });
    dist[node] = 0;
    
    while(!pq.empty()) {
        auto now = pq.top();
        int v = now.second;
        int e = now.first;
        pq.pop();

        for(auto g : graph[v]) {
            int next = g.first;
            int nextVal = g.second + e;
            if(dist[next] > nextVal) {
                dist[next] = nextVal;
                pq.push({ nextVal, next });
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 2147000000;
    for(auto f : fares) {
        graph[f[0]].push_back({ f[1], f[2] });
        graph[f[1]].push_back({ f[0], f[2] });
    }
    for(int i = 1; i <= n; i++) {
        dist[i] = 2147000000;
    }
    D(s);
    
    for(int i = 1; i <= n; i++) {
        tmp[i] = dist[i];
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            dist[j] = 2147000000;
        }
        D(i);
        int sum = tmp[i] + dist[a] + dist[b];
        // cout << sum << "\n";
        answer = min(answer, sum);
    }
    return answer;
}

/*
n : 지점 갯수
s : 출발지점
a : A 도착지점
b : B 도착지점


*/