[백준 / BOJ] C++ 13168 내일로 여행

13168번: 내일로 여행

 

문제

https://www.acmicpc.net/problem/13168

13168번: 내일로 여행

 

 

풀이

여러 도시와 도시 간 이동 가능한 교통수단을 입력받고 정해진 순서대로 특정 도시들을 여행하는 최소 비용을 구하는 문제다. 단, 여기서 '내일로'라는 티켓을 구매하면 특정 교통수단은 0원이거나 반값이 된다. 이때 '내일로' 티켓을 구매하는 것이 더 비용이 적게 드는지 구하는 문제다.

 

특정 도시를 정점으로 사용하기 위해 map을 사용해 도시마다 번호를 붙였다. 그리고 여행 경로를 정점 번호로 저장한 다음 각 교통 수단을 입력받는다. 플로이드-워셜 알고리즘을 사용해 문제를 풀 것이기 때문에 각 정점간 거리를 구하는 dist 배열을 2개 만들었다. dist1은 '내일로' 티켓을 구매하지 않았을 경우, dist2는 구매했을 경우다. 입력으로 들어오는 정점 간 비용을 양방향으로 dist1 배열에 저장한다. 교통 수단이 '내일로' 티켓으로 할인되거나 0원인 경우엔 dist2 배열에 해당 경로 값이 더 작은 경우만 저장한다.

 

그리고 각 배열에 대해 플로이드-워셜 알고리즘을 적용한 후, 여행 경로를 따라가며 비용을 각각 더한다. dist1, dist2에 대응하는 합을 sum1, sum2라 했을 때 sum1 > sum2 + R(티켓 값)인 경우가 티켓을 샀을 때 비용이 더 싼 경우다.

 

*주의 (99퍼에서 틀리는 경우)*

가격이 반값인 경우, 정수가 아닌 실수형(float, double) 자료형을 사용해야 한다. 당연히 sum도 실수형이어야 한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, R, M, K;
  double dist1[101][101], dist2[101][101];
  map<string, int> m;
  cin >> N >> R;
  // 입력받는 순서대로 1~N번 도시
  for (int i = 1; i <= N; i++) {
    string s;
    cin >> s;
    m[s] = i;
  }
  cin >> M;
  vector<int> v;
  // 여행 경로를 정점 번호로 저장
  for (int i = 1; i <= M; i++) {
    string s;
    cin >> s;
    v.push_back(m[s]);
  }
  // dist 배열 초기화
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
      dist1[i][j] = i == j ? 0 : INF;
      dist2[i][j] = i == j ? 0 : INF;
    }
  cin >> K;
  // 간선 입력
  while (K--) {
    string t, s, e; // 교통수단, 시작점, 도착점
    double c; // 비용
    cin >> t >> s >> e >> c;
    int u = m[s], v = m[e]; // 시작/도착 도시의 번호
    // 티켓을 구매하지 않은 경우
    dist1[u][v] = min(dist1[u][v], c);
    dist1[v][u] = min(dist1[v][u], c);
    // 티켓을 구매한 경우
    if (t == "Mugunghwa" || t == "ITX-Saemaeul" || t == "ITX-Cheongchun") { // 기차값이 0원인 경우
      dist2[u][v] = 0;
      dist2[v][u] = 0;
    } else if (t == "S-Train" || t == "V-Train") { // 기차값이 반값인 경우
      dist2[u][v] = min(dist2[u][v], c / 2);
      dist2[v][u] = min(dist2[v][u], c / 2);
    } else { // 할인이 없는 경우
      dist2[u][v] = min(dist2[u][v], c);
      dist2[v][u] = min(dist2[v][u], c);
    }
  }
  // 플로이드-워셜
  for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++) {
        dist1[i][j] = min(dist1[i][j], dist1[i][k] + dist1[k][j]);
        dist2[i][j] = min(dist2[i][j], dist2[i][k] + dist2[k][j]);
      }
  // 티켓을 사지 않은/산 경우 최소 비용 구하기
  double sum1 = 0, sum2 = 0;
  for (int i = 0; i < M - 1; i++) {
    int s = v[i], e = v[i + 1];
    sum1 += dist1[s][e];
    sum2 += dist2[s][e];
  }
  // 티켓을 산 경우 가격이 더 싸면 Yes, 아니면 No
  cout << (sum1 > sum2 + R ? "Yes\n" : "No\n");
  return 0;
}