[알고리즘] 백준 > #13168. 내일로 여행

문제링크

백준 #13168. 내일로 여행

풀이방법

모든 도시 사이의 거리를 구해야하는 문제라 플로이드 와샬 알고리즘을 이용해 해결했다. 교통수단을 입력받을 때부터 내일로를 이용한 경우, 그렇지 않은 경우를 구분했다. 내일로를 이용하는 경우, 교통수단의 타입과 가격을 getPriceWithPass 메소드로 전달해 할인된 가격을 리턴받았다. 그리고 매번 교통수단이 입력될 때 만약 도시와 도시 사이에 이미 다른 교통수단이 있었으면 최소 값만 저장했다. 그 외에는 일반적인 플로이드 와샬 문제와 동일했다! 도시가 문자열로 주어졌는데, 문자열을 그대로 사용하려면 Map을 사용해야돼서 (도시의 문자열 값 -> 도시의 int id 값)으로 바꾸는 부분만 Map을 사용했다!

코드

import java.util.*;

public class BOJ13168 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int passPrice = sc.nextInt();

        HashMap<String, Integer> cityMap = new HashMap<>();
        for (int i = 0 ; i < n; i++) cityMap.put(sc.next(), i); // 0 - seoul, 1 - busan ...

        int m = sc.nextInt();
        int[] travels = new int[m];
        for (int i = 0; i < m; i++) {
            String city = sc.next();

            travels[i] = cityMap.get(city); // 0 - 2- 5 - ...
        }

        Double[][] transportations = new Double[n][n];
        Double[][] transportationsWithPass = new Double[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                transportations[i][j] = 1000000001.0;
                transportationsWithPass[i][j] = 1000000001.0;

                if (i == j) {
                    transportations[i][j] = 0.0;
                    transportationsWithPass[i][j] = 0.0;
                }
            }
        }
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            String type = sc.next();
            int cityA = cityMap.get(sc.next());
            int cityB = cityMap.get(sc.next());
            int price = sc.nextInt();

            transportations[cityA][cityB] = Math.min(transportations[cityA][cityB], price);
            transportations[cityB][cityA] = Math.min(transportations[cityB][cityA], price);

            Double priceWithPass = getPriceWithPass(price, type);
            transportationsWithPass[cityA][cityB] = Math.min(transportationsWithPass[cityA][cityB], priceWithPass);
            transportationsWithPass[cityB][cityA] = Math.min(transportationsWithPass[cityB][cityA], priceWithPass);
        }

        for (int city = 0; city < n; city++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    transportations[i][j] = Math.min(transportations[i][j], transportations[i][city] + transportations[city][j]);
                    transportationsWithPass[i][j] = Math.min(transportationsWithPass[i][j], transportationsWithPass[i][city] + transportationsWithPass[city][j]);
                }
            }
        }

        Double totalPrice = 0.0;
        Double totalPriceWithPass = Double.valueOf(passPrice);

        for (int i = 1; i < m; i++) {
            totalPrice += transportations[travels[i - 1]][travels[i]];
            totalPriceWithPass += transportationsWithPass[travels[i - 1]][travels[i]];
        }

        if (totalPrice > totalPriceWithPass) System.out.print("Yes");
        else System.out.print("No");
    }

    static private Double getPriceWithPass(int price, String type) {
        if ((type.equals("Mugunghwa")) || (type.equals("ITX-Cheongchun") || (type.equals("ITX-Saemaeul")))) return 0.0;
        else if ((type.equals("S-Train") ||(type.equals("V-Train")))) return price / 2.0;
        else return Double.valueOf(price);
    }
}