[BOJ/Floyd-Warshall] 백준 13168 - 내일로 여행 (Java)

백준 13168 - 내일로 여행

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

문제

입력
첫 번째 줄: 한국에 있는 도시 수 N (1 <= N <= 100), 1인당 내일로 티켓 가격 R (1 <= R <= 1,000,000)
두 번째 줄: N개의 도시 이름 (알파벳 대소문자로 구성된 길이 <= 20 문자열)
세 번째 줄: 여행할 도시 수 M (1 <= M <= 200)
네 번째 줄: 여행할 M개 도시 이름 (N개 도시 중 하나)
다섯 번째 줄: 교통수단의 수 K (1 <= K <= 10,000)
마지막 K개 줄: 교통수단 정보 (종류 Type, 양 끝 도시 S_i, E_i, 1인당 비용 Cost_i (1 <= Cost_i <= 100,000))
모든 도시는 주어진 K개의 교통수단 이용해서 갈 수 있음
/ 이름이 같은 도시가 있을 수 있음
-> N개 도시의 이름에는 같은 도시의 이름 2번 이상 주어질 수 있고 이 경우 모두 같은 도시라고 생각해야 함 
출력: 내일로 티켓을 사는 것이 좋으면 Yes / 그렇지 않으면 No
(내일로 티켓 사더라도 비용이 같으면 No)

---

풀이

도시 이름, 여행 경로 문자열로 주어짐 -> 0 ~ N - 1 정수로 매핑

Map<String, Integer> HM = new HashMap<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
    String name = st.nextToken();
    if (!HM.containsKey(name)) HM.put(name, HM.size());
}

int[] travel = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
    travel[i] = HM.get(st.nextToken());
}

 

자기 자신으로 가는 경로의 최단 비용 0 / 나머지 `INF`로 초기화

• `double[][] normal`: 일반 비용
• `double[][] rail`: 할인 비용

double[][] normal = new double[N][N];
double[][] rail = new double[N][N];
for (int i = 0; i < N; i++) {
    Arrays.fill(normal[i], INF);
    Arrays.fill(rail[i], INF);
    normal[i][i] = 0;
    rail[i][i] = 0;
}

 

양방향 노선 -> 두 방향 모두 `Math.min()`으로 설정

• `normal[a][b]`, `normal[b][a]`
• `rail[a][b]`, `rail[b][a]`
  • 열차 종류 -> 무료/할인/정가 => `getRailCost(String type, double cost)`

static double getRailCost(String type, double cost) {
    if (type.equals("Mugunghwa") || type.equals("ITX-Saemaeul") || type.equals("ITX-Cheongchun")) return 0;
    else if (type.equals("S-Train") || type.equals("V-Train")) return cost / 2.0;
    return cost;
}

normal[a][b] = Math.min(normal[a][b], cost);
normal[b][a] = Math.min(normal[b][a], cost);

double railCost = getRailCost(type, cost);
rail[a][b] = Math.min(rail[a][b], railCost);
rail[b][a] = Math.min(rail[b][a], railCost);

 

모든 쌍 최단 거리(Floyd–Warshall)

for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            normal[i][j] = Math.min(normal[i][j], normal[i][k] + normal[k][j]);
            rail[i][j] = Math.min(rail[i][j], rail[i][k] + rail[k][j]);
        }
    }
}

 

• 일반 여행(`normal`): 각 구간 비용 전부 더함
• 내일로 여행(`rail`): `R`(티켓값) + 할인된 구간 비용들의 합

double normalCost = 0;
double railCost = R;

for (int i = 0; i < M - 1; i++) {
    int from = travel[i];
    int to = travel[i + 1];

    normalCost += normal[from][to];
    railCost += rail[from][to];
}

---

코드

import java.io.*;
import java.util.*;

// 내일로 여행
public class boj_13168 {
    static int N, R, M, K;
    static final double INF = 1_000_000_000;

    static double getRailCost(String type, double cost) {
        if (type.equals("Mugunghwa") || type.equals("ITX-Saemaeul") || type.equals("ITX-Cheongchun")) return 0;
        else if (type.equals("S-Train") || type.equals("V-Train")) return cost / 2.0;
        return cost;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        Map<String, Integer> HM = new HashMap<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            String name = st.nextToken();
            if (!HM.containsKey(name)) HM.put(name, HM.size());
        }

        M = Integer.parseInt(br.readLine());

        int[] travel = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            travel[i] = HM.get(st.nextToken());
        }

        K = Integer.parseInt(br.readLine());
        
        double[][] normal = new double[N][N];
        double[][] rail = new double[N][N];

        for (int i = 0; i < N; i++) {
            Arrays.fill(normal[i], INF);
            Arrays.fill(rail[i], INF);
            normal[i][i] = 0;
            rail[i][i] = 0;
        }

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            String type = st.nextToken();
            String s = st.nextToken();
            String e = st.nextToken();
            double cost = Double.parseDouble(st.nextToken());

            int a = HM.get(s);
            int b = HM.get(e);

            normal[a][b] = Math.min(normal[a][b], cost);
            normal[b][a] = Math.min(normal[b][a], cost);

            double railCost = getRailCost(type, cost);
            rail[a][b] = Math.min(rail[a][b], railCost);
            rail[b][a] = Math.min(rail[b][a], railCost);
        }

        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    normal[i][j] = Math.min(normal[i][j], normal[i][k] + normal[k][j]);
                    rail[i][j] = Math.min(rail[i][j], rail[i][k] + rail[k][j]);
                }
            }
        }

        double normalCost = 0;
        double railCost = R;
        for (int i = 0; i < M - 1; i++) {
            int from = travel[i];
            int to = travel[i + 1];

            normalCost += normal[from][to];
            railCost += rail[from][to];
        }

        System.out.println(railCost < normalCost ? "Yes" : "No");
    }
}