[BOJ] 10217: KCM Travel (C/C++)

게시 2025/09/02 업데이트 2025/09/10

By SeungJae Oh

12 분읽는 시간

문제 10217번: KCM Travel

각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다.

초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, 다가올 결승 대회를 생각하면 대회 외적인 곳에 마음을 쓰고 싶지 않은 것 또한 사실이었다. 그래서 찬민은 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 길을 차선책으로 택하기로 하였다.

각 공항들간 티켓가격과 이동시간이 주어질 때, 찬민이 인천에서 LA로 갈 수 있는 가장 빠른 길을 찾아 찬민의 대회 참가를 도와주자.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. T는 항상 1이다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 공항의 수 N (2 ≤ N ≤ 100), 총 지원비용 M (0 ≤ M ≤ 10,000), 티켓정보의 수 K (0 ≤ K ≤ 10,000)가 공백으로 구분되어 주어진다. 이어서 K개의 줄에 걸쳐 각 티켓의 출발공항 u, 도착공항 v (1 ≤ u, v ≤ N, u ≠ v), 비용 c (1 ≤ c ≤ M, 정수), 그리고 소요시간 d (1 ≤ d ≤ 1,000) 가 공백으로 구분되어 주어진다. 인천은 언제나 1번 도시이고, LA는 언제나 N번 도시이다

출력

각 테스트 케이스당 한 줄에 찬민이 LA에 도착하는 데 걸리는 가장 짧은 소요시간을 출력한다.

만약, LA에 도착할 수 없는 경우 “Poor KCM”을 출력한다.

문제분석

문제 요구사항

도시를 Vertex, 티켓을 Directed Edge로 해석 할 수 있음
비용이 M이하인 Shortest Path를 구해야 함

Shortest Path를 구하기 위하여 Dijkstra 알고리즘을 사용
Dijkstra 알고리즘의 효율화를 위해 Priority Queue와 Dynamic Programming을 활용

구현

Priority Queue의 top에 나올수 있는 Route 들의 이미 진행된 Route들에 대비하여 나올 수 있는 경우의 수를 따져보자

	경우의 수
낮은 소요시간, 낮은 비용	낮은 소요시간, 동일 비용	낮은 소요시간, 높은 비용
X	X	X
동일 소요시간, 낮은 비용	동일 소요시간, 동일 비용	동일 소요시간, 높은 비용
O	O	O
높은 소요시간, 낮은 비용	높은 소요시간, 동일 비용	높은 소요시간, 높은 비용
O	O	O

이떄 유효한 경우의 수만 따져보게 되면

	유효한 경우의 수
낮은 소요시간, 낮은 비용	낮은 소요시간, 동일 비용	낮은 소요시간, 높은 비용
X	X	X
동일 소요시간, 낮은 비용	동일 소요시간, 동일 비용	동일 소요시간, 높은 비용
O	X	X
높은 소요시간, 낮은 비용	높은 소요시간, 동일 비용	높은 소요시간, 높은 비용
O	X	X

이떄 유효하지 않은 4가지 경우의 수를 필터링 하기 위하여 Dynamic Programming을 이용하여 구현한다.

증명

유효하지 않은 4가지 경우의 수를 필터링 하기 위하여 dp[도시][비용] = 소요시간 인 matrix를 선언한다.
이떄 유효하지 않은 Route들의 경우 비용이 동일하고 같거나, 소요시간이 동일하거나 같은 경우이다.
Priority Queue에 이러한 data가 들어오지 않게 하기 위하여, 새로 만들어진 Route가 Priority Queue에 들어오기 전, 소요시간이 동일하거나 같은 경우에 Priority Queue에 push하지 않는다.
유효한 Route가 Priority Queue에 push된 경우, 아직 탐색되지 않은 Route가 현재 Route와 같은 비용인 경우 자기 자신보다 낮은 소요시간을 가지는 Route가 유효하기에 현재 route의 비용 뿐만아니라 현재 Route비용 이상의 탐색되지 않은 Route들의 소요시간도 update 해준다.

여담

Dijkstra알고리즘과 Dynamic Programming을 사용한 코드 뿐만 아닌, 더 최적화되어 있는 Dynamic Programming만 사용된 코드도 같이 게재하였다.

코드

Priority Queue and Dynamic Programming

  
#include <algorithm>
#include <climits>
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
#include <vector>

constexpr int INF = INT_MAX >> 1;

struct Route {
  int v;
  int c;
  int d;
  Route() : v(0), c(0), d(0) {}
  Route(const int v, const int c, const int d) : v(v), c(c), d(d) {}
  Route(const Route& r) : v(r.v), c(r.c), d(r.d) {}
  Route operator=(const Route& r) {
    this->v = r.v;
    this->c = r.c;
    this->d = r.d;
    return *this;
  }
  const bool operator<(const Route& r) const {
    return this->d != r.d   ? this->d < r.d
           : this->c != r.c ? this->c < r.c
                            : this->v > r.v;
  }

  const bool operator>(const Route& r) const {
    return this->d != r.d   ? this->d > r.d
           : this->c != r.c ? this->c > r.c
                            : this->v < r.v;
  }
};

std::istream& operator>>(std::istream& is, Route& r) {
  is >> r.v >> r.c >> r.d;
  return is;
}

std::ostream& operator<<(std::ostream& os, const Route& r) {
  os << r.v << " " << r.c << " " << r.d;
  return os;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);

  int T;
  std::cin >> T;

  for (int i = 0; i < T; ++i) {
    int N, M, K;
    std::cin >> N >> M >> K;
    std::cin.ignore();

    std::vector<std::vector<Route>> routes(N + 1);
    std::string input;
    std::stringstream buffer;
    for (int j = 0; j < K; ++j) {
      std::getline(std::cin, input);
      buffer << input;

      int u;
      Route temp_route;
      buffer >> u >> temp_route;
      buffer.clear();

      routes[u].push_back(temp_route);
    }

    for (auto& j : routes) {
      std::sort(j.begin(), j.end(), std::less<Route>());
    }

    std::vector<std::vector<int>> dp(N + 1, std::vector<int>(M + 1, INF));
    std::priority_queue<Route, std::vector<Route>, std::greater<Route>> pq;
    pq.push(Route(1, 0, 0));

    while (!pq.empty() && pq.top().v != N) {
      Route now_r(pq.top());
      pq.pop();

      if (dp[now_r.v][now_r.c] < now_r.d) {
        continue;
      }
      dp[now_r.v][now_r.c] -= 1;
      for (auto& j : routes[now_r.v]) {
        Route new_r(j.v, now_r.c + j.c, now_r.d + j.d);
        if (new_r.c > M || dp[new_r.v][new_r.c] <= new_r.d) {
          continue;
        }
        pq.push(new_r);
        for (int k = new_r.c; k < dp[now_r.v].size(); ++k) {
          if (dp[new_r.v][k] < new_r.d) {
            break;
          }
          dp[new_r.v][k] = new_r.d;
        }
      }
    }

    if (pq.empty()) {
      std::cout << "Poor KCM\n";
    } else {
      std::cout << pq.top().d << "\n";
    }
  }

  return 0;
}

Dynamic Programming

  
#include <algorithm>
#include <climits>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

constexpr int INF = INT_MAX >> 1;

struct Route {
  int v;
  int c;
  int d;
  Route() : v(0), c(0), d(0) {}
  Route(const int v, const int c, const int d) : v(v), c(c), d(d) {}
  Route(const Route& r) : v(r.v), c(r.c), d(r.d) {}
  Route operator=(const Route& r) {
    this->v = r.v;
    this->c = r.c;
    this->d = r.d;
    return *this;
  }
  const bool operator<(const Route& r) const { return this->c < r.c; }

  const bool operator>(const Route& r) const { return this->c > r.c; }
};

std::istream& operator>>(std::istream& is, Route& r) {
  is >> r.v >> r.c >> r.d;
  return is;
}

std::ostream& operator<<(std::ostream& os, const Route& r) {
  os << r.v << " " << r.c << " " << r.d;
  return os;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);

  int T;
  std::cin >> T;

  for (int i = 0; i < T; ++i) {
    int N, M, K;
    std::cin >> N >> M >> K;
    std::cin.ignore();

    std::vector<std::vector<Route>> routes(N);
    std::string input;
    std::stringstream buffer;
    for (int j = 0; j < K; ++j) {
      std::getline(std::cin, input);
      buffer << input;

      int u;
      Route temp_route;
      buffer >> u >> temp_route;
      buffer.clear();
      temp_route.v -= 1;
      routes[u - 1].push_back(temp_route);
    }

    for (auto& j : routes) {
      std::sort(j.begin(), j.end(), std::less<Route>());
    }

    std::vector<std::vector<int>> dp(N, std::vector<int>(M + 1, INF));
    dp[0][0] = 0;

    for (int i = 0; i <= M; ++i) {
      for (int j = 0; j < N; ++j) {
        if (dp[j][i] == INF) {
          continue;
        }
        for (auto& route : routes[j]) {
          const Route new_route(route.v, route.c + i, route.d + dp[j][i]);
          if (new_route.c > M) {
            break;
          }
          dp[new_route.v][new_route.c] =
              std::min(dp[new_route.v][new_route.c], new_route.d);
        }
      }
    }

    int ans = INF;
    for (auto i : dp.back()) {
      ans = std::min(ans, i);
    }

    if (ans == INF) {
      std::cout << "Poor KCM\n";
    } else {
      std::cout << ans << "\n";
    }
  }

  return 0;
}

Algorithm, problems