[BOJ] 백준 13168 : 내일로 여행 (java)

• 🧪 13168 내일로 여행

• 📝 문제

• 🧐 핵심 로직 

• 💻 최종 코드 (360 ms)

🧪 13168 내일로 여행

---

난이도 : 🌟 골드 3
유형 : 플로이드-워셜

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

 

📝 문제

---

친한 친구인 승현이와 지학이는 여름방학 때 여행을 가기로 계획했습니다. 해외여행은 금전적으로 부담이 많기 때문에 둘은 한국의 여러 도시를 여행하기로 했습니다. 한국에는 N개의 도시가 있으며, 승현이는 이 중 여행할 M개의 도시를 결정했습니다. 여행 경로에서 같은 도시를 여러 번 방문할 수 있으며, 여행을 시작하는 도시와 끝내는 도시는 같습니다.

한국에는 두 도시 사이를 오갈 수 있는 K개의 교통수단이 있습니다. 교통수단의 종류는 기차, 지하철, 버스, 택시, 비행기 등으로 다양합니다. 특히 기차 코스는 매우 세부적으로 나뉘어 있어서 무궁화호(Mugunghwa), ITX-새마을(ITX-Saemaeul), ITX-청춘(ITX-Cheongchun), KTX, S-Train, V-Train 등이 있습니다. 모든 교통수단은 한 번 이용하는 데 필요한 비용이 정해져 있습니다. 승현이와 지학이는 계획한 M개의 도시를 최소비용으로 차례대로 움직일 것입니다.

한편, 코레일에서는 ‘내일로’라는 특별한 기차표를 판매하고 있습니다. 방학 동안, 젊은 청년들은 R원을 주고 내일로 티켓을 살 수 있습니다. 한 번 내일로 티켓을 사면, 며칠 동안 무궁화호, ITX-새마을, ITX-청춘은 무료로 이용할 수 있으며, S-Train과 V-Train은 50% 할인된 가격으로 이용할 수 있습니다. KTX나 지하철, 또는 다른 교통수단에 대해서는 할인이 적용되지 않습니다.

지학이는 자신이 아무것도 하지 않는 것에 죄책감을 느끼기 때문에, 자신들의 여행에서 내일로 티켓이 필요한지 생각해보기로 했습니다. 지학이를 도와 내일로 티켓을 사는 것과 사지 않는 것 중 어떤 선택이 더 좋은 지 구하는 프로그램을 작성하세요.

 

입력

 

첫 번째 줄에는 한국에 있는 도시의 수 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개의 줄에는 교통수단에 대한 정보가 주어집니다. 줄마다 교통수단의 종류 Typei, 양 끝 도시 Si, Ei, 1인당 비용 Costi (1 ≤ Costi ≤ 100,000)가 주어집니다. Typei는 ‘Subway’, ‘Bus’, ‘Taxi’, ‘Airplane’, ‘KTX’, ‘S-Train’, ‘V-Train’, ‘ITX-Saemaeul’, ‘ITX-Cheongchun’, ‘Mugunghwa’ 중 하나이며, 모든 도시는 주어진 K개의 교통수단을 이용하여 갈 수 있음이 보장되어 있습니다.

한국에는 이름이 같은 도시가 있을 수 있다. 따라서, N개의 도시의 이름에는 같은 도시의 이름이 두 번 이상 주어질 수도 있다. 이 경우 이러한 도시를 모두 같은 도시라고 생각해야 한다.

 

출력

 

 

한줄에 내일로 티켓을 사는 것이 좋으면 ‘Yes’를 출력하고 그렇지 않으면 ‘No’를 출력합니다. 내일로 티켓을 사더라도 비용이 정확히 같다면 ‘No’를 출력합니다.

 

🧐 핵심 로직 

---

1. 장소 정보를 저장하고 번호를 부여한다.

    1 - 1) removeDuplicate() 메서드를 통해 중복된 장소를 제거하고, places 배열에 저장한다.

    1 - 2)  각 장소에 고유한 번호를 부여하여 numberingPlaces 맵에 저장한다.

 

2. 이동 비용을 저장하는 배열을 초기화한다.

    2 - 1)  costs 배열과 costWithTickets 배열을 생성하고 initialize() 메서드에서 초기화한다.

    2 - 2)   같은 장소 간 비용은 0, 나머지 장소 간 비용은 INF로 설정한다.

 

3. 입력된 이동 정보를 기반으로 그래프를 구성한다.

    3 - 1)   connectPlace() 메서드에서 입력을 읽어 출발지와 도착지를 numberingPlaces를 통해 번호로 변환한다.

    3 - 2)   기본 이동 비용(costs)과 정기권이 적용된 비용(costWithTickets)을 비교하며 최소 비용을 저장한다.

    3 - 3)   calculateTicket() 메서드를 이용하여 교통수단별 정기권 할인율을 반영한다.

 

4. 플로이드-워셜 알고리즘을 사용하여 모든 장소 간 최단 비용을 계산한다.

    4 - 1)   floydWarshall() 메서드를 통해 모든 장소에서 모든 장소로 가는 최소 비용을 갱신한다.

    4 - 2)   중간 경유지를 고려하여 비용을 갱신하면서 최단 경로를 찾는다.

 

5. 여행 경로의 총 비용을 계산하고, 정기권 적용 여부를 비교한다.

    5 - 1)   compareResult() 메서드에서 여행 경로에 따라 이동 비용을 합산한다.

    5 - 1)   정기권을 사용했을 때(sumWithTickets + r)와 사용하지 않았을 때(sum)의 비용을 비교하여 "Yes" 또는 "No"를 출력한다.

 

💻 최종 코드 (360 ms)

---

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

public class Main {

    static BufferedReader br;
    static int n, r, m, k, placeSize;
    static int INF = 987654321;
    static String[] places;
    static String[] trip;
    static Map<String, Integer> numberingPlaces;
    static double[][] costs;
    static double[][] costWithTickets;
    public static void main(String[] args) throws Exception {

//      br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st1 = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st1.nextToken());
        r = Integer.parseInt(st1.nextToken());

        removeDuplicate(br.readLine().split(" "));

        m = Integer.parseInt(br.readLine());
        trip = new String[m];
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            trip[i] = st2.nextToken();
        }

        k = Integer.parseInt(br.readLine());
        connectPlace();
        floydWarshall();
        compareResult();

        br.close();
    }

    private static void removeDuplicate(String[] arr) {

        Set<String> setPlaces = new HashSet<>(Arrays.asList(arr));
        places = setPlaces.toArray(String[]::new);
        placeSize = places.length;

        numberingPlaces = new HashMap<>();
        for (int i = 0; i < placeSize; i++) {
            numberingPlaces.put(places[i], i);
        }
    }

    private static void connectPlace() throws Exception {

        costs = new double[placeSize][placeSize];
        costWithTickets = new double[placeSize][placeSize];
        initialize();
        for (int i = 0; i < k; i++) {
            String[] input = br.readLine().split(" ");
            String type = input[0];
            String start = input[1];
            String end = input[2];
            double cost = Double.parseDouble(input[3]);
            double costWithTicket = calculateTicket(type, cost);

            int u = numberingPlaces.get(start);
            int v = numberingPlaces.get(end);
            costs[u][v] = Math.min(costs[u][v], cost);
            costs[v][u] = Math.min(costs[v][u], cost);
            costWithTickets[u][v] = Math.min(costWithTickets[u][v], costWithTicket);
            costWithTickets[v][u] = Math.min(costWithTickets[v][u], costWithTicket);
        }
    }

    private static double calculateTicket(String type, double cost) {

        Set<String> free = new HashSet<>(List.of("Mugunghwa", "ITX-Saemaeul", "ITX-Cheongchun"));
        Set<String> discount = new HashSet<>(List.of("S-Train", "V-Train"));

        if (free.contains(type)) {
            return 0;
        } else if (discount.contains(type)) {
            return 0.5 * cost;
        }

        return cost;
    }

    private static void initialize() {

        for (int i = 0; i < placeSize; i++) {
            for (int j = 0; j < placeSize; j++) {
                if (i != j) {
                    costs[i][j] = INF;
                    costWithTickets[i][j] = INF;
                }
            }
        }
    }

    private static void floydWarshall() {

        for (int k = 0; k < placeSize; k++) {
            for (int u = 0; u < placeSize; u++) {
                for (int v = 0; v < placeSize; v++) {
                    costs[u][v] = Math.min(costs[u][v], costs[u][k] + costs[k][v]);
                    costWithTickets[u][v] = Math.min(costWithTickets[u][v], costWithTickets[u][k] + costWithTickets[k][v]);
                }
            }
        }
    }

    private static void compareResult() {

        double sum = 0;
        double sumWithTickets = 0;
        for (int i = 0; i < trip.length - 1; i++) {
            int u = numberingPlaces.get(trip[i]);
            int v = numberingPlaces.get(trip[i + 1]);

            sum += costs[u][v];
            sumWithTickets += costWithTickets[u][v];
        }

        System.out.println(sumWithTickets + r < sum ? "Yes" : "No");
    }
}