[C++로 풀이] 합승 택시 요금 (플로이드 와샬, 다익스트라)⭐⭐⭐

📌 합승 택시 요금

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

(i = 1,2,3,..,n) S 에서 출발해서 i 까지 합승하고, 그 이후엔 따로 따로 i 에서 A 까지, i 에서 B 까지 가는 최소 택시비용 구하기

즉, 이 문제는 ⭐최소비용(S 👉 i) + 최소비용(i 👉 A) + 최소비용(i 👉 B)⭐ 을 구하면 되는 문제이다. i 까지만 합승하고 i 에서는 A, B 따로 가기기 떄문에 구해야하는 최단 경로(=최소 비용)은 3 가지이며 모든 i (= 1,2,3,..,n) 에 대하여 다 구해보고 세 최소비용을 더한 최종 값이 가장 작은 경우를 답으로 도출하면 된다! 가장 작은 택시비용이 도출되는 경우가 i 라면 i까지만 합승하는게 가장 비용이 적게 든다는 이야기다.

따라서 최단 경로 알고리즘을 적용하면 되는데, 다익스트라를 사용할 수도 있지만 출발지 정점이 여러가지이므로 모든 정점에서 모든 정점까지인 모든 쌍의 최단 경로를 한번에 구하는 플로이드 와샬 알고리즘을 생각해볼 수도 있다.

---

• 1️⃣ 플로이드 와샬
  • 모든 정점들끼리의 최단 경로를 한번에 구한다. 즉, 모든 정점들끼리 짝지은 ‘한 쌍’별로 최단 경로를 Dynamic Programming 방식으로 다 구한다.
  • 모두 구하고나면 모든 정점들끼리의 ‘쌍’별로 최단 경로들이 저장된 이차원 테이블이 완성될텐데
    • 모든 i = 1,2,3,..,n 중에서 dp[s][i] + dp[i][a] + dp[i][b] 결과가 가장 최소값일 때가 바로 합승택시 최저 요금이된다.
• 2️⃣ 다익스트라
  • 하나의 시작 정점에서 모든 정점들까지의 최단 경로를 구한다.
    • 최소비용(S 👉 i) : 시작점 S 부터 모든 정점들까지의 최단 경로
    • 최소비용(i 👉 A) : 시작점 A 부터 모든 정점들까지의 최단 경로
      • 사실 시작점은 모든 정점을 뜻하는 i 고 도착점이 A 인 것이지만 이는 곧 A를 시작점으로 하고 모든 정점들까지의 “최단 경로”와도 완전히 동일하다. 즉, i -> A 최소비용은 A -> i 최소 비용과도 같다. 따라서 A를 시작점으로 삼은 다익스트라를 진행해도 이와 동일한 결과를 얻을 수 있다.
    • 최소비용(i 👉 B) : 마찬가지로 시작점 B 부터 모든 정점들까지의 최단 경로

이 2 가지 알고리즘으로 각각 풀이를 진행해보았다.

---

🔥 플로이드 와샬 ⭕

#include <string>
#include <vector>

using namespace std;

#define INF 20000000

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    vector<vector<int>> minTaxiCost(n + 1, vector<int>(n + 1, INF)); // 모든 정점들간의 최단 경로를 저장할 (i, j) 2차원 dp 테이블
    
    /* 준비 작업 : (i, j) 는 곧 "i -> 중간에 들리는 정점들 -> j" 의 최단 경로인데, 아직 중간에 뭘 들리기 전, 즉 i->j 직빵 연결된 가중치들이 있다면 기록 */
    for(int i = 0; i < fares.size(); ++i){ 
        minTaxiCost[fares[i][0]][fares[i][1]] = fares[i][2];
        minTaxiCost[fares[i][1]][fares[i][0]] = fares[i][2];
    }   

    /* 준비 작업 : dp[i][i] 자기 자신에서 자기 자신으로의 최단 경로는 0 으로 초기화 (대각선) */  
    for(int i = 1; i <= n; ++i)
        minTaxiCost[i][i] = 0;

    /* 플로이드 알고리즘 핵심  */
    for(int k = 1; k <= n; ++k) // ⭐k 를 거쳐갈 때⭐
        for(int i = 1; i <= n; ++i) // (i, j) : i->j 최단 경로
            for(int j = 1; j <= n; ++j) 
                if (minTaxiCost[i][j] > minTaxiCost[i][k] + minTaxiCost[k][j]) // i 에서 j 로 갈 때 k 를 거쳐가는게 더 좋은 최단 경로가 된다면 업데이트
                    minTaxiCost[i][j] = minTaxiCost[i][k] + minTaxiCost[k][j];

    // 위까지만 완료하면 minTaxiCost 테이블에 모든 (i, j) 정점 쌍의 i->j 최단 경로가 저장되게 된다.
    // 답 도출! 모든 정점(i)에 대하여 dp[s][i] + dp[i][a] + dp[i][b] 가 가장 최소가 될 때의 비용
    for(int i = 1; i <= n; ++i)
        if (answer > minTaxiCost[s][i] + minTaxiCost[i][a] + minTaxiCost[i][b])
            answer = minTaxiCost[s][i] + minTaxiCost[i][a] + minTaxiCost[i][b];
          
    return answer;
}

(C++) 플로이드 와샬 Floyd Warshall (+ 최단 경로 알고리즘 비교)

1. 모든 (i, j) 정점 쌍의 i->j 최단 경로가 저장된 테이블을 완성한 후
2. s 부터 i 까지의 최단 경로(=i까지 합승) + i 부터 a 까지의 최단 경로(i에서 내려서 따로 감) + i 부터 b 까지의 최단 경로(i에서 내려서 따로 감)
   • 中 가장 최소가 되는 비용 도출

플로이드 와샬 문제의 핵심은 첫 번째 for문의 ⭐k 를 거쳐갈 때⭐ 이 부분이라고 생각된다. 첫번째 for문을 중간에 거쳐갈 정점으로 두기 때문에 i->1->j 1을 거쳐가는게 빠른지 아닌지를 판단하여 테이블의 모든 요소(i, j)가 업데이트 되고, 이 1을 거쳐갈지 말지가 고려된 이.후.에 ! 다음 for문 반복으로 i->2->j 2을 거쳐가는게 빠른지 아닌지를 판단하고 이 전제 위에다가 다음 반복때 3을 걸쳐갈지 말지가 판단되기 때문에 결국, 모든 정점들이 중간 경로가 되는 것이 적당한지 한 번씩 검사를 받게 된다. 따라서 이와 같은 원리로 정점간의 최단 경로 비용을 담은 테이블이 완성된다.

🔥 다익스트라

✈ 1 차 풀이 ⏰(시간초과)

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

using namespace std;
#define INF 20000000
#define num first 
#define cost second 

struct cmp {
    bool operator() (pair<int, int> a, pair<int, int> b) {
        return a.cost > b.cost; // min-heap
    }
};
/* start -> dest 최단 경로 구하기 */
int dijkstra(vector<vector<int>>& graph, int& n, int& start, int& dest) {
    vector<int> taxi_cost(n + 1, INF); // start 부터 각각의 정점까지의 최소 비용
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

    /* 출발지 예약 */
    pq.push({ start, 0 });
    taxi_cost[start] = 0;

    while (!pq.empty()) {
        /* 방문 */
        int now = pq.top().num;
        int nowCost = pq.top().cost;
        pq.pop();

        // dest 방문(pop)하면 바로 종료시키기로 했다.
        if (now == dest) //  방문했다는 것은 같은 정점 중에서 가장 최단 경로를 가진 정점이 빠져나왔다는 뜻이므로 dest 에 방문하면 종료해도 된다.
            break;
        
        /* 예약 */ 
        for (int i = 1; i <= n; ++i) {
            if (graph[now][i] == 0) // 예약 조건 1. 방문한 정점과 연결되어 있는 정점들에 대해서만 진행
                continue;

            if (taxi_cost[i] > nowCost + graph[now][i]) { // 예약 조건 2. 기존에 구한 최단 경로보다 현재 방문 정점을 통해서 이 정점에 가는 것이 더 빠른 경우 예약.
                taxi_cost[i] = nowCost + graph[now][i];
                pq.push({ i, nowCost + graph[now][i] });
            }
        }
    }

    return taxi_cost[dest]; // start -> dest 최단경로 리턴
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;

    vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0)); // 그래프 정보
    for (int i = 0; i < fares.size(); ++i) {
        graph[fares[i][0]][fares[i][1]] = fares[i][2];
        graph[fares[i][1]][fares[i][0]] = fares[i][2];
    }

    for (int i = 1; i <= n; ++i) { // i 까지만 합승할 때의 택시 비용 계산
        int result = dijkstra(graph, n, s, i) + dijkstra(graph, n, i, a) + dijkstra(graph, n, i, b);
        if (answer > result) // answer 에 여태까지 나온 총 택시 비용 중 최소값 담기
            answer = result;
    }

    return answer;
}

시간 초과가 발생하는 풀이였다. 내가 시간 초과의 이유는 매 정점마다 다익스트라를 3 번씩 구했기 때문이였던 것 같다. 즉, 정점이 6개라면 난 다익스트라 알고리즘을 18번 연산한 셈이다.

• 2️⃣ 다익스트라
  • 하나의 시작 정점에서 모든 정점들까지의 최단 경로를 구한다.
    • 최소비용(S 👉 i) : 시작점 S 부터 모든 정점들까지의 최단 경로
    • 최소비용(i 👉 A) : 시작점 A 부터 모든 정점들까지의 최단 경로
      • 사실 시작점은 모든 정점을 뜻하는 i 고 도착점이 A 인 것이지만 이는 곧 A를 시작점으로 하고 모든 정점들까지의 “최단 경로”와도 완전히 동일하다. 즉, i -> A 최소비용은 A -> i 최소 비용과도 같다. 따라서 A를 시작점으로 삼은 다익스트라를 진행해도 이와 동일한 결과를 얻을 수 있다.
    • 최소비용(i 👉 B) : 마찬가지로 시작점 B 부터 모든 정점들까지의 최단 경로

위에서 작성한 이 부분으로 알 수 있지만 정점 마다 3 번씩 구할게 아니라 (1️⃣시작점 S 부터 모든 정점들까지의 최단 경로, 2️⃣시작점 A 부터 모든 정점들까지의 최단 경로, 3️⃣시작점 B 부터 모든 정점들까지의 최단 경로) 이렇게 3 번만 다익스트라를 연산하면 된다는 것을 깨달았다. 출발 정점을 기준으로 최소 비용을 구하기 때문에 출발지가 다를 때마다 최소 비용 결과도 달라진다. 따라서 S시작, A시작, B시작 이렇게 3 개의 최소 비용 vector 를 따로 따로 두고 이에 다익스트라 결과를 각각 받아놓은 후에 최소 택시 비용을 구하여 시간을 줄여보기로 했다. 이러면 다익스트라 연산을 정점의 개수와 상관없이 딱 3 번만 진행하면 됐다.

✈ 2 차 풀이 ⭕

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

using namespace std;
#define INF 20000000
#define num first 
#define cost second 

struct cmp {
    bool operator() (pair<int, int> a, pair<int, int> b) {
        return a.cost > b.cost;
    }
};

// taxi_cost 추가! (파라미터로 받는 vector 에 최소 비용을 업데이트 할 것이다. 즉, 출발지가 다를 때마다 최소 비용 vector도 따로따로)
// dest 없앴음 (어차피 출발지에서 모든 정점으로의 최단 경로를 구할 것이라서)
void dijkstra(vector<int>& taxi_cost, vector<vector<int>>& graph, int& n, int& start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

    pq.push({ start, 0 });
    taxi_cost[start] = 0;

    while (!pq.empty()) {
        int now = pq.top().num;
        int nowCost = pq.top().cost;
        pq.pop();
           
        for (int i = 1; i <= n; ++i) {

            if (graph[now][i] == 0)
                continue;

            if (taxi_cost[i] > nowCost + graph[now][i]) {
                taxi_cost[i] = nowCost + graph[now][i];
                pq.push({ i, nowCost + graph[now][i] });
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;

    vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < fares.size(); ++i) {
        graph[fares[i][0]][fares[i][1]] = fares[i][2];
        graph[fares[i][1]][fares[i][0]] = fares[i][2];
    }
    // S 를 출발 정점으로 한 모든 정점까지의 최단 경로 구하여 StoI_cost 에 저장
    vector<int> StoI_cost(n + 1, INF);
    dijkstra(StoI_cost, graph, n, s);
    
    // A 를 출발 정점으로 한 모든 정점까지의 최단 경로 구하여 AtoI_cost 에 저장
    vector<int> AtoI_cost(n + 1, INF);
    dijkstra(AtoI_cost, graph, n, a);
    
    // B 를 출발 정점으로 한 모든 정점까지의 최단 경로 구하여 BtoI_cost 에 저장
    vector<int> BtoI_cost(n + 1, INF);
    dijkstra(BtoI_cost, graph, n, b);

    // (s->i) + (a->i) + (b->i) 택시비용중 최소가 되는 비용
    for (int i = 1; i <= n; ++i) {
        int result = StoI_cost[i] + AtoI_cost[i] + BtoI_cost[i];
        if (answer > result)
            answer = result;
    }

    return answer;
}

시간 초과 해결 ~.~

🚀 시간복잡도 비교

다익스트라를 사용했을 때가 가장 시간 효율성이 좋았다.

• 플로이드 와샬 👉 \(O(V^3)\)
  • 모든 정점들간의 최단 경로 (i,j)를 차례 차례 i->1->j 이렇게 1을 거칠 때, 이것을 전제로 i->2->j 이렇게 2을 거칠 때.. 이런식으로 연산하기 때문에 정점을 3 중 for문 순회하게 된다.
• 다익스트라 👉 O(3 * (VlogV + ElogV)) = O((V + E)logV) = O(ElogV)
  • 우선순위 큐에서 최단 경로를 가진 정점 꺼내서 방문
    • V * logV
      • 모든 정점마다 한번씩 방문하게 됨 V
      • 루트를 pop 하고 다시 힙정렬하는 과정이 logV
    • E * logV
      • 이웃 정점을 예약하는건 곧 간선을 검사하는 것과 같다. E
      • 이웃 정점 push 하고 다시 힙정렬하는 과정이 logV

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기