C++ 프로그램으로 기차 이동 시 출발역에서 목적역까지 필요한 최소 시간 구하기

n개의 역이 m개의 선로로 연결되어 있다고 가정해 보겠습니다. 역에는 1부터 n까지 번호가 매겨져 있으며, 모든 선로는 양방향으로 통행할 수 있습니다. 우리의 목표는 src 역에서 dst 역까지 이동하는 것입니다.

i번째 철도 노선의 양쪽 역 정보는 배열 roads에 담겨 있으며, 각 원소는 {station1, station2} 형식입니다. 또한 j번째 역에서는 그 역과 연결된 모든 역으로 향하는 기차가 kj 시간의 배수가 되는 시각마다 출발하고, 기차가 목적 역에 도착하는 데는 tj만큼의 시간이 걸립니다. 이 값들은 배열 departure에 {tj, kj} 형식으로 주어집니다. 우리가 구해야 할 것은 src에서 dst까지 이동하는 데 필요한 최소 시간입니다. 중간에 여러 번 환승할 수 있으며, 환승에 소요되는 시간은 무시할 수 있습니다.

예를 들어 입력이 다음과 같다고 합시다.

n = 4, m = 3, src = 1, dst = 4, roads = {{1, 2}, {2, 4}, {3, 4}}, departure = {{2, 1}, {3, 5}, {7, 6}}

이때 출력은 8이 됩니다. 1번 역에서 시각 0에 출발하는 기차를 타고 2번 역으로 이동하면 도착까지 2의 시간이 걸립니다. 이후 2번 역에서 시각 5에 출발하는 기차를 타고 4번 역으로 가면 3의 시간이 추가됩니다. 따라서 총 소요 시간은 (5 + 3) = 8입니다.

풀이 접근 방법

이 문제는 다익스트라(Dijkstra) 최단 경로 알고리즘을 기차 시간표 상황에 맞게 변형하여 해결할 수 있습니다. 각 역에 도착하는 최소 시간을 추적하되, 인접 역으로 이동할 때는 다음 기차의 출발 시각(kj의 배수)을 고려해 실제 도착 시각을 계산하는 것이 핵심입니다. 구현에서는 시간을 음수로 저장함으로써 최대 힙 기반 우선순위 큐를 최소 시간 기준으로 활용합니다.

해결 과정은 다음과 같습니다 −

src := src - 1
dst := dst - 1
튜플을 저장하는 새 배열 graph[n] 정의
i := 0으로 초기화하고, i < m 동안 i를 1씩 증가시키며 반복:
   a := roads[i]의 첫 번째 값 - 1
   b := roads[i]의 두 번째 값 - 1
   t := departure[i]의 첫 번째 값
   k := departure[i]의 두 번째 값
   graph[a]의 끝에 튜플 (b, t, k) 추가
   graph[b]의 끝에 튜플 (a, t, k) 추가
크기가 n이고 초기값이 -9999인 배열 dp 정의
쌍(pair)을 저장하는 우선순위 큐 priq 정의
dp[src] := 0
priq의 끝에 쌍 (-dp[src], src) 삽입
priq가 비어 있지 않은 동안 반복:
   (w, a)를 포함하는 튜플 := priq의 최댓값
   priq에서 맨 위 원소 제거
   만약 a가 dst와 같으면:
      -w 반환
   만약 w < dp[a]이면:
      아래 부분을 무시하고 다음 반복으로 건너뜀
   graph[a]의 각 원소 v에 대해:
      (b, t, k)를 포함하는 튜플 생성
      weight := (w - k + 1) / k * k - t
      만약 weight > dp[b]이면:
         dp[b] := weight
         priq의 끝에 쌍 (weight, b) 삽입
-1 반환

여기서 핵심 식인 weight = (w - k + 1) / k * k - t는 현재 시각 이후 가장 빠르게 출발하는 기차의 출발 시각(kj의 배수)을 구한 뒤, 이동 시간 t를 더해 다음 역에 도착하는 시각을 계산합니다. 이를 통해 기다리는 시간까지 반영된 실제 도착 시각으로 최단 시간을 갱신할 수 있습니다.

예제

아래 구현을 통해 더 자세히 이해해 보겠습니다 −

#include <bits/stdc++.h>
using namespace std;

int solve(int n, int m, int src, int dst, vector<pair<int, int>> roads, vector<pair<int, int>> departure){
   src -= 1; 
   dst -= 1;
   vector<tuple<int, int, int>> graph[n];
   int a, b;
   int t, k;
   for(int i = 0; i < m; i++){
      a = roads[i].first - 1;
      b = roads[i].second - 1;
      t = departure[i].first;
      k = departure[i].second;
      graph[a].emplace_back(b, t, k);
      graph[b].emplace_back(a, t, k);
   }
   vector<int> dp(n, -9999);
   priority_queue<pair<int, int>> priq; 
   dp[src] = 0;
   priq.push(make_pair(-dp[src], src));
   int w;
   while(not priq.empty()){
      tie(w, a) = priq.top();
      priq.pop(); if(a == dst){
         return -w;
      }
      if(w < dp[a]) 
         continue;
      for(auto &v: graph[a]){
         tie(b, t, k) = v;
         int weight = (w - k + 1) / k * k - t; 
         if(weight > dp[b]){
            dp[b] = weight;
            priq.push(make_pair(weight, b));
         }
      }
   }
   return -1;
}
int main() {
   int n = 4, m = 3, src = 1, dst = 4;
   vector<pair<int, int>>
   roads = {{1, 2}, {2, 4}, {3, 4}},
   departure = {{2, 1}, {3, 5}, {7, 6}};
   cout<< solve(n, m, src, dst, roads, departure);
   return 0;
}

입력

4, 3, 1, 4, {{1, 2}, {2, 4}, {3, 4}}, {{2, 1}, {3, 5}, {7, 6}}