[프로그래머스] 합승 택시 요금 2021 카카오 블라인드 테스트 level3

문제 :

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

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

 

분석 :

첫번째 접근 

문제를 보아하니 a와 b가 따로 갔을때와 중간 지점 걸쳐서 도착한 요금 중 최소 요금을 출력하라는 말을 보고 최단 경로를 떠올렸다. 그래서 다익스트라로 접근하면 되겠구나 하고 

s 출발지점에서   int cost =  dijkstra(s, a) + dijkstra(s, b); a는 a 도착지까지 최단 경로 + b는 b 도착지까지 최단 경로를 더한 cost값과

중간 지점을 거쳐 간 경우 cost = min(cost, dijkstra(i, a) + dijkstra(i, b) + dijkstra(s, i)); for문을 돌려 모든 노드에 대해 i 중간 지점을 거쳐 간 경우 중 최단 경로를 구하는 방식으로 하면 되겠다 했다.

하지만 시간 초과 .. no ...

 

그래서 플로이드 와샬로 접근하는게 오히려 빠를 수도 있다 하는데 

내 코드에서 시간을 줄일 수 있는 부분을 찾아보기로 했다. 

main 함수에서 다익스트라 함수를 부를때 3중 for문이 되므로 이 부분에서 다익스트라를 적게 부르는 방법에 대해 생각하면 될것 같았다.

 

c++ 코드 : 시간 초과 난 코드 😵 

//
//  [KAKAO] 2021_sharedTaxi.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/28.
//

#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>

#define INF 1e9

using namespace std;
priority_queue<pair<int, int>> pq;
vector<pair<int, int>> vertex[201];

int d[201]; //거리의 합

int dijkstra(int start, int end){
    fill(d, d+201, INF);
    pq.push({0, start});
    d[start] = 0;
    while(!pq.empty()){
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();

        for (int i = 0; i< vertex[now].size(); i++) {
            int cost = dist + vertex[now][i].second;
            if(cost <d[vertex[now][i].first]) // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            {
                d[vertex[now][i].first] = cost;
                pq.push(make_pair(-cost, vertex[now][i].first));
            }

        }
    }


    return d[end];
}

int main(){
    // n - 지점의 개수, s - 시작, a - a 도착 , b - b 도착
    int n = 6; int s =4; int a = 5; int b = 6;
//    vector<vector<int>> fares = {{4, 1, 10}, {3, 5, 24}, {5, 6, 2}, {3, 1, 41}, {5, 1, 24}, {4, 6, 50}, {2, 4, 66}, {2, 3, 22}, {1, 6, 25}};

//    vector<vector<int>> fares = {{5, 7, 9}, {4, 6, 4}, {3, 6, 1}, {3, 2, 3}, {2, 1, 6}};

    vector<vector<int>> fares = {{2, 6, 6}, {6, 3, 7}, {4, 6, 7}, {6, 5, 11}, {2, 5, 12}, {5, 3, 20}, {2, 4, 8}, {4, 3, 9}};

    for(int i = 0; i < fares.size(); i++){//9
        vertex[fares[i][0]].push_back({fares[i][1], fares[i][2]});
        vertex[fares[i][1]].push_back({fares[i][0], fares[i][2]});
    }

    //따로 갔을때의 비용
    int cost =  dijkstra(s, a) + dijkstra(s, b);
    //중간 지점 거쳐 갔을때의 비용
    for(int i = 1; i<= n; i++){
        if (i != s){//4가 아닐때
            if(dijkstra(i, a) == 1000000000 || dijkstra(i, b) == 1000000000) continue; //떨어져 있으므로 못감

            cost = min(cost, dijkstra(i, a) + dijkstra(i, b) + dijkstra(s, i));
        }
    }
    cout << cost << '\n';

    return 0;
}

 

2개의 시간 초과 외의 진전된 코드 🆗🙆🏻

 

개선한 사항 : 거리를 계산할 때 도착지까지의 최단 거리를 반환하는 int 형 함수에서 void 함수로 바꾸었고 main 함수 내에 필요한 최단 경로 구하는 배열을 생성하여 함수 호출 없이 배열의 값 참조 형식으로 바꾸었다.

//
//  [KAKAO] 2021_sharedTaxi.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/28.
//

#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>

#define INF 1e9

using namespace std;
priority_queue<pair<int, int>> pq;
vector<pair<int, int>> vertex[201];


void dijkstra(int d[], int start){
    fill(d, d+201, INF);
    pq.push({0, start});
    d[start] = 0;
    while(!pq.empty()){
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
   
        for (int i = 0; i< vertex[now].size(); i++) {
            int cost = dist + vertex[now][i].second;
            if(cost <d[vertex[now][i].first]) // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            {
                d[vertex[now][i].first] = cost;
                pq.push(make_pair(-cost, vertex[now][i].first));
            }

        }
    }

}

int main(){
    // n - 지점의 개수, s - 시작, a - a 도착 , b - b 도착
    int n = 6; int s =4; int a = 5; int b = 6;
//    vector<vector<int>> fares = {{4, 1, 10}, {3, 5, 24}, {5, 6, 2}, {3, 1, 41}, {5, 1, 24}, {4, 6, 50}, {2, 4, 66}, {2, 3, 22}, {1, 6, 25}};
    
//    vector<vector<int>> fares = {{5, 7, 9}, {4, 6, 4}, {3, 6, 1}, {3, 2, 3}, {2, 1, 6}};
    
    vector<vector<int>> fares = {{2, 6, 6}, {6, 3, 7}, {4, 6, 7}, {6, 5, 11}, {2, 5, 12}, {5, 3, 20}, {2, 4, 8}, {4, 3, 9}};
    
    for(int i = 0; i < fares.size(); i++){//9
        vertex[fares[i][0]].push_back({fares[i][1], fares[i][2]});
        vertex[fares[i][1]].push_back({fares[i][0], fares[i][2]});
    }
    
    // - 추가한 사항 -
    int sd[201]; //거리의 합
    int id[201]; //거리의 합
    dijkstra(sd, s);
    //따로 갔을때의 비용
    int cost =  sd[a] + sd[b];
    //중간 지점 거쳐 갔을때의 비용
    for(int i = 1; i<= n; i++){
    // (이 부분에서 마찬가지로 시간초과가 나는 듯 하다)
        dijkstra(id, i);
        if (i != s){//4가 아닐때
            if(id[a] == 1000000000 || id[b] == 1000000000 ) continue; //떨어져 있으므로 못감
            
            cost = min(cost, id[a] + id[b] + sd[i]);
        }
    }
    cout << cost << '\n';

    return 0;
}

 

결과 :

 

두개가 맘에 걸리지만 .. 다음에 와서 더 효율적인 코드로 풀기로 🥲