백준 13168 - 내일로 여행

문제

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

리뷰

플로이드-워셜을 응용하여 풀이할 수 있는 문제였다. 까다로운 부분이 있었다면
기존의 정점을 번호로 표현하는 여타 문제들과 다르게 정점이 문자열의 형태(도시이름)으로
주어지고, 교통수단의 종류에 따라 경로 $i \rightarrow j$의 비용을 다르게 설정해주어야
구현하는 것이 아니었나 싶다.

우선 도시 이름으로 표현되는 정점들을 정점 번호로 치환하기 위해 Map 을 활용하여
각 도시이름들을 정점번호로 매핑하였다. 이후 방문할 도시들을 순서에 따라 List에 저장하였다.

한편, Transportation이라는 별도의 클래스를 정의하여 교통 수단의 종류, 연결하는 두 도시,
비용 정보를 저장할 수 있도록 정의했다. 이를 이용해 List에 교통 수단들을 정보를 저장했다.

티켓을 구매하는 경우와 하지 않는 경우의 비용을 구하는 로직은 다음과 같이 전개된다.

• initMap 을 통해 플로이드-워셜을 실행할 map 을 초기화한다.
• setCostByTicket을 통해 티켓 구매 여부에 따른 비용을 map에 저장한다. 여기에
  transportationList와 citiesMap을 사용하였다.
• floyd 를 사용해 모든 경로의 최소 비용을 도출한다.

이후 단순히 두 비용을 비교하여 Yes, No를 출력해주면 된다.

문제를 풀이하며 애먹었던 부분은 비용을 50% 할인하는 조건을 구현할 때 비용의 타입을
결정하는 부분이었다. 99%에서 오답을 몇 번 마주하며 아예 비용과 관련된 변수들의
모든 타입을 double로 바꾸었다.

로직의 시간 복잡도는 $O(N^3)$으로 수렴하므로 주어진 $N$이 최대인 $100$일 경우에도
주어진 시간 제한 조건인 1초를 무난히 통과한다.

코드

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

import static java.lang.Integer.parseInt;
import static java.lang.Double.parseDouble;
import static java.lang.Integer.MAX_VALUE;

public class Main {
    static int N, R;
    static Map<String, Integer> citiesMap = new HashMap<>();
    static List<String> visitedCities = new ArrayList<>();
    static List<Transportation> transportationList = new ArrayList<>();
    static double[][] map;

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

        st = new StringTokenizer(br.readLine()); // O(N)
        for (int i = 1; i <= N; i++)
            citiesMap.put(st.nextToken(), i);
        map = new double[N + 1][N + 1];

        int M = parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++)              // O(M)
            visitedCities.add(st.nextToken());

        int K = parseInt(br.readLine());
        for (int i = 0; i < K; i++) {           // O(K)
            st = new StringTokenizer(br.readLine());
            String type = st.nextToken();
            String start = st.nextToken();
            String end = st.nextToken();
            double cost = parseDouble(st.nextToken());

            transportationList.add(new Transportation(type, start, end, cost));
        }

        initMap(); // O(N^2)
        setCostByTicket(0); // O(K)
        floyd(); // O(N^3)

        double costWithoutTicket = calculateCost(); // O(M)

        initMap();
        setCostByTicket(1);
        floyd();

        double costWithTicket = calculateCost() + R;

        System.out.print((costWithTicket < costWithoutTicket) ? "Yes" : "No");
        br.close();
    }

    static double calculateCost() {
        String current, next;
        double sum = 0;

        for (int i = 0; i < visitedCities.size() - 1; i++) {
            current = visitedCities.get(i);
            next = visitedCities.get(i + 1);

            int start = citiesMap.get(current);
            int end = citiesMap.get(next);

            sum += map[start][end];
        }

        return sum;
    }

    static void floyd() {
        for (int k = 1; k < map.length; k++)
            for (int i = 1; i < map.length; i++)
                for (int j = 1; j < map.length; j++) {
                    if (map[i][k] == MAX_VALUE || map[k][j] == MAX_VALUE)
                        continue;

                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
    }

    static void setCostByTicket(int ticket) {
        for (Transportation t : transportationList) {
            int u = citiesMap.get(t.start);
            int v = citiesMap.get(t.end);

            switch (t.type) {
                case "Mugunghwa":
                case "ITX-Saemaeul":
                case "ITX-Cheongchun":
                    if (ticket == 1) {
                        map[u][v] = Math.min(map[u][v], 0);
                        map[v][u] = Math.min(map[v][u], 0);
                    } else {
                        map[u][v] = Math.min(map[u][v], t.cost);
                        map[v][u] = Math.min(map[v][u], t.cost);
                    }
                    break;
                case "S-Train":
                case "V-Train":
                    if (ticket == 1) {
                        map[u][v] = Math.min(map[u][v], t.cost * 0.5);
                        map[v][u] = Math.min(map[v][u], t.cost * 0.5);
                    } else {
                        map[u][v] = Math.min(map[u][v], t.cost);
                        map[v][u] = Math.min(map[v][u], t.cost);
                    }
                    break;

                default:
                    map[u][v] = Math.min(map[u][v], t.cost);
                    map[v][u] = Math.min(map[v][u], t.cost);
            }
        }
    }

    static void initMap() {
        for (int i = 0; i < map.length; i++)
            for (int j = 0; j < map[i].length; j++) {
                if (i == j) {
                    map[i][j] = 0;
                    continue;
                }

                map[i][j] = MAX_VALUE;
            }
    }

    static class Transportation {
        String type;
        String start, end;
        double cost;

        public Transportation(String type, String start, String end, double cost) {
            this.type = type;
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }
}

결과