[Programmers] Lv3. 합승 택시 요금 | C++

🔗문제 보러가기

프로그래머스

 

🧑🏻‍💻 풀이 과정

 

[1차 시도] 다익스트라 알고리즘 (실패)

 

출발지(s)로부터 각 노드에 대한 최단 경로 배열을 구해놓고, 각 노드(i)마다 다익스트라 알고리즘을 돌려서 s👉🏻i + i👉🏻a + i👉🏻b 값들 중 최솟값을 구하는 방식으로 풀었습니다. 노드의 개수(N)가 최대 200개라 될 줄 알았는데 효율성 테스트에서 시간 초과가 나더군요.

 

[2차 시도] 플로이드 워셜 알고리즘 (성공)

 

매 노드마다 다익스트라 알고리즘을 돌린 것이 원인이라 생각되어, 모든 노드 간의 최단 경로를 구할 수 있는 플로이드 워셜 알고리즘을 사용했습니다. 사실 옛날에 써 보고 안 써서 기억이 안 났는데, 간단한 알고리즘이라 빨리 공부하고 풀 수 있었네요.

 

 

✏️소스 코드 및 결과

#include <vector>
using namespace std;
using uint32 = unsigned int;
#define INF 3000000000

void FloydWarshall(vector<vector<uint32>>& graph, int n)
{
    for (int mid = 1; mid <= n; mid++)
        for (int from = 1; from <= n; from++)
            for (int to = 1; to <= n; to++)
                graph[from][to] = min(graph[from][to], graph[from][mid] + graph[mid][to]);
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {

    // 1. Input Initialize
    vector<vector<uint32>> graph(n + 1, vector<uint32>(n + 1, INF));
    for (int i = 1; i <= n; i++)
        graph[i][i] = 0;
    
    for (const vector<int>& fare : fares)
    {
        uint32 from = fare[0], to = fare[1], cost = fare[2];
        graph[from][to] = graph[to][from] = cost;
    }

    // 2. Floyd-Warshall Algorithm
    FloydWarshall(graph, n);
    uint32 answer = INF;

    for (int i = 1; i <= n; i++)
        answer = min(answer, graph[s][i] + graph[i][a] + graph[i][b]);
    return answer;
}