2021 KAKAO BLIND RECRUITMENT > 합승 택시 요금

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

다익스트라 알고리즘의 응용 문제이다.

 

일반적으로라면 무조건 최단거리를 구하면 되겠지만 합석도 고려해야 한다.

따라서 어느 지점에서 합석을 취소하여 거기서부터 최소비용 거리를 구해야하는 것이다.

 

이를 위해서 모든 지점에 대한 최단거리를 구한 다음 이를 순회하여 그 합이 최소가 되도록 한다.

 

시작점에서의 모든 점에 대한 다익스트라 결과 배열

A에서의 B에서의 각각 출발하여 모든 점에서의 다익스트라 결과를 순회하도록 하는 것이다.

 

문제의 표현을 따르자면 시작점에서 출발하여 i 노드에서 A와 B까지 최소비용거리로 나아가는 것이다.

 

이는 문제에서의 조건이 방향이 무관한 간선으로 이루어졌기 때문이다.

 

문제가 풀기 복잡하여 개념을 공공하기 위해 각 줄 마다 모두 주석을 넣어 표시하였다.

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>  // INT_MAX를 포함하는 헤더

using namespace std;

// 다익스트라 알고리즘을 통해 최단 거리를 계산하는 함수
vector<int> Dijkstra(int s, const vector<vector<int>>& graph) {
    int n = graph.size();  // 그래프의 크기(노드 수)를 n에 저장
    vector<int> distance(n, INT_MAX);  // 모든 노드의 초기 거리를 무한대로 설정
    distance[s] = 0;  // 시작 지점 s의 거리는 0으로 설정
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  // 최소 힙(우선순위 큐) 생성
    pq.push({0, s});  // 시작 지점을 큐에 추가 (거리, 노드)

    while (!pq.empty()) {  // 큐가 빌 때까지 반복
        int dist = pq.top().first;  // 큐의 최상단 노드의 거리 값
        int node = pq.top().second;  // 큐의 최상단 노드 번호
        pq.pop();  // 큐에서 최상단 노드 제거

        // 이미 더 짧은 경로로 도달한 노드인 경우 현재 경로를 무시하고 건너뜀
        // 최단 경로가 아닌 경로를 탐색하는 것을 방지하여 효율성을 높임
        if (dist > distance[node]) continue;

        // 현재 노드에서 모든 이웃 노드로 가는 경로를 확인
        for (int i = 0; i < n; i++) {  // 현재 노드의 모든 이웃 노드 확인
            if (graph[node][i] != 0) {  // 현재 노드에서 i로 가는 간선이 있는지 확인
                int newDist = dist + graph[node][i];  // 새로운 거리 계산
                if (newDist < distance[i]) {  // 새로운 거리가 기존 거리보다 짧으면 업데이트
                    distance[i] = newDist;  // 거리 배열에 새로운 거리 저장
                    pq.push({newDist, i});  // 우선순위 큐에 새 거리와 노드 추가
                }
            }
        }
    }

    return distance;  // 시작 지점에서 모든 노드까지의 최단 거리를 반환
}

// 주어진 조건에 맞는 최소 이동 비용을 계산하는 함수
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    // 그래프를 인접 행렬 형태로 초기화
    vector<vector<int>> graph(n, vector<int>(n, 0));
    for (const vector<int>& fare : fares) {  // 각 운임 정보에 대해 반복
        int u = fare[0] - 1;  // 첫 번째 노드 (1부터 시작하는 인덱스이므로 1을 빼줌)
        int v = fare[1] - 1;  // 두 번째 노드
        int cost = fare[2];   // 두 노드 사이의 비용
        graph[u][v] = cost;  // 무방향 그래프이므로 양쪽에 비용 저장
        graph[v][u] = cost;
    }

    // 각 출발 지점에서 다른 노드까지의 최단 거리를 계산
    vector<int> distFromStart = Dijkstra(s - 1, graph);  // 출발 지점 s에서 다른 노드까지
    vector<int> distFromA = Dijkstra(a - 1, graph);      // 도착 지점 a에서 다른 노드까지
    vector<int> distFromB = Dijkstra(b - 1, graph);      // 도착 지점 b에서 다른 노드까지

    int answer = INT_MAX;  // 최소 비용을 구하기 위해 초기값을 무한대로 설정
    for (int i = 0; i < n; i++) {  // 모든 노드를 중간 지점으로 고려하여 반복
        // 중간 지점까지의 최단 거리 중 하나라도 무한대라면 건너뜀
        // INT_MAX는 도달할 수 없는 경로를 의미하므로, 유효한 경로가 아님
        if (distFromStart[i] == INT_MAX || distFromA[i] == INT_MAX || distFromB[i] == INT_MAX) continue;
        
        // 유효한 경로에 대해 중간 지점 i를 통해 이동하는 비용을 계산하고, 최소값으로 업데이트
        answer = min(answer, distFromStart[i] + distFromA[i] + distFromB[i]);
    }

    return answer;  // 계산된 최소 비용을 반환
}