[JAVA] 백준 13168번 【G3.내일로 여행】

문제

13168번: 내일로 여행

 

풀이

1️⃣ 플로이드 알고리즘과 해시를 이용한 풀이

💡 떠오른 Idea

먼저, 플로이드 알고리즘을 사용해서 도시와 도시간 어떤 경로를 거치던 최소 비용을 구해야겠다고 생각이 들었다.

다만, 이 문제의 경우 도시가 숫자가 아닌 문자열의 형태로 주어지기 때문에

도시를 고유한 숫자로 변환하여 플로이드 알고리즘을 사용해야겠다는 생각이 들었다.

1. 먼저, 주어지는 도시의 중복이 있을 수 있다고 했으므로 중복을 제거한다.

중복을 제거한 뒤, map을 정의하여 각 도시의 이름을 Key로 하고 번호를 0부터 부여한다.

2. 도시와 도시로의 교통수단 정보를 받을 때, map에서 도시 이름으로 도시 번호를 얻어올 수 있게 된다.

번호로 변환한 도시 2개를 이용하여 비용을 2차원 배열 그래프에 입력해주면된다.

내일로 티켓을 사용한 비용 배열과 아닌 배열 2개를 정의하여 따로 입력해준다.

3. 내일로 티켓을 사용했다고 가정한 비용과 일반 비용 2개의 배열을 각각 플로이드 알고리즘을 통해

각 도시에서 도시로의 최소 비용 배열을 구한다.

4. 계획한 여행 루트를 바탕으로 각 경우의 비용 총합을 구하고 비교하여 답을 반환한다.

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int numOfCities = Integer.parseInt(input[0]);
        int R = Integer.parseInt(input[1]);
        final int MAX = 10000100;

        // 도시 중복 제거
        String[] places = getPlaces(br.readLine().split(" "));

        // 도시 별 번호 부여
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < places.length; i++) {
            map.put(places[i], i);
        }

        // 중복을 제거한 도시의 수
        int N = map.size();

        int M = Integer.parseInt(br.readLine());
        // 여행할 도시 순서
        String[] trip = br.readLine().split(" ");


        int K = Integer.parseInt(br.readLine());
        // 내일로 할인이 적용 안되는 비용
        double[][] costs = new double[N][N];
        // 내일로 할인이 적용되는 비용
        double[][] costsWithTicket = new double[N][N];

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (r != c) {
                    costs[r][c] = MAX;
                    costsWithTicket[r][c] = MAX;
                }
            }
        }

        // 도시에서 도시로 이동하는 비용 입력
        for (int i = 0; i < K; i++) {
            input = br.readLine().split(" ");
            String type = input[0];
            String start = input[1];
            String end = input[2];
            double cost = Double.parseDouble(input[3]);

            // 교통 수단에 따른 할인가 계산
            double costWithTicket = calculatePrice(type, cost);

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

        // 플로이드 알고리즘 사용
        for (int m = 0; m < N; m++) {
            for (int u = 0; u < N; u++) {
                for (int v = 0; v < N; v++) {
                    costs[u][v] = Math.min(costs[u][v], costs[u][m] + costs[m][v]);
                    costsWithTicket[u][v] = Math.min(costsWithTicket[u][v], costsWithTicket[u][m] + costsWithTicket[m][v]);
                }
            }
        }

        // 도시에서 도시로 가는 최소비용이 플로이드를 통해 계산 되었으므로 총 합을 구한다.
        double sum = 0;
        double sumWithTicket = 0;

        for (int i = 0; i < M - 1; i++) {
            int u = map.get(trip[i]);
            int v = map.get(trip[i + 1]);
            sum += costs[u][v];
            sumWithTicket += costsWithTicket[u][v];
        }

        System.out.println(sum <= sumWithTicket + R ? "No" : "Yes");
    }

    private static String[] getPlaces(String[] arr) {
        Set<String> set = new HashSet<>();

        for (String city : arr) {
            set.add(city);
        }

        return set.stream().toArray(String[]::new);
    }

    private static double calculatePrice(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;
        } else {
            return cost;
        }
    }
}

 

결과