백준 13168 (내일로 여행) - java

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의 크기가 100이고 문제를 해결하기 위해서는 각 지점에서 나머지 모든 다른 지점으로의 최단 비용 정보를 가지고 있어야 한다.
• 가장 정석적인 방식은 플로이드 - 워셜을 사용하는 것이다. 하지만 나는 다익스트라를 사용했다. (사실 속도 측면에서도 플로이드 - 워셜이 더 빠르다)
• dis[][] 배열은 내일로를 구매하지 않는 경우고 tDis[][]배열은 내일로를 구매한 경우다.
• 그리고 / 연산을 할 때 홀수를 나누는 경우를 고려해야 하기 때문에 double을 사용하거나 거리 값을 입력 받을 때부터 2배해서 풀면 된다.

 

전체 코드

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

public class Main {
    static int n,m,k;
    static double r;

    static PriorityQueue<Point> pq = new PriorityQueue<>(
            (x,y) -> Double.compare(x.c,y.c)
    );
    static int[] path;
    static HashMap<String,Integer> map1 = new HashMap<>();

    static double[][] dis;

    static double[][] tDis;
    static ArrayList<Node>[] graph;

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

        n = Integer.parseInt(st.nextToken());
        r = Double.parseDouble(st.nextToken());

        graph = new ArrayList[n+1];
        dis = new double[n+1][n+1];
        tDis = new double[n+1][n+1];

        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= n ; j++) {
                if(i == j)
                    continue;

                dis[i][j] = Double.MAX_VALUE;
                tDis[i][j] = Double.MAX_VALUE;
            }
        }

        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= n ; i++) {
            String cur = st.nextToken();
            map1.put(cur,i);
            graph[i] = new ArrayList<>();
        }

        st = new StringTokenizer(br.readLine()," ");
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine()," ");
        path = new int[m+1];

        for(int i = 1 ; i <= m ; i++) {
            path[i] = map1.get(st.nextToken());
        }

        st = new StringTokenizer(br.readLine()," ");
        k = Integer.parseInt(st.nextToken());

        for(int i = 1 ; i <= k ; i++) {
            st = new StringTokenizer(br.readLine()," ");

            String w = st.nextToken();
            int v1 = map1.get(st.nextToken());
            int v2 = map1.get(st.nextToken());
            double c = Double.parseDouble(st.nextToken());

            graph[v1].add(new Node(w,v2,c));
            graph[v2].add(new Node(w,v1,c));
        }

        for(int i = 1 ; i <= n ; i++) {
            notUse(i);
            use(i);
        }

        double noUseResult = 0;
        double useResult = 0;

        for(int i = 1 ; i < m ; i++) {
            noUseResult += dis[path[i]][path[i+1]];
            useResult += tDis[path[i]][path[i+1]];
        }


        if(noUseResult > useResult + r) {
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }



        br.close();
    }

    static void use(int idx) {
        pq.clear();
        pq.add(new Point(idx,0));

        while(!pq.isEmpty()) {
            Point cur = pq.poll();

            for(Node next : graph[cur.v]) {
                double nextC = next.c;
                String nextW = next.w;

                if(nextW.equals("Mugunghwa") || nextW.equals("ITX-Saemaeul") || nextW.equals("ITX-Cheongchun")) {
                    nextC = 0;
                }else if(nextW.equals("S-Train") || nextW.equals("V-Train")) {
                    nextC /= 2;
                }

                if(tDis[idx][next.v] > cur.c + nextC) {
                    tDis[idx][next.v] = cur.c + nextC;
                    pq.add(new Point(next.v,tDis[idx][next.v]));
                }
            }
        }
    }

    static void print(int[][] dis) {
        for(int i =1 ; i <= n ; i++) {
            for(int j =1 ; j <= n ; j++) {
                System.out.print(dis[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }
    static void notUse(int idx) {
        pq.clear();
        pq.add(new Point(idx,0));

        while(!pq.isEmpty()) {
            Point cur = pq.poll();

            for(Node next : graph[cur.v]) {
                if(dis[idx][next.v] > cur.c + next.c) {
                    dis[idx][next.v] = cur.c + next.c;
                    pq.add(new Point(next.v,dis[idx][next.v]));
                }
            }
        }
    }

    static class Point {
        int v;
        double c;

        Point(int v,double c) {
            this.v = v;
            this.c = c;
        }
    }

    static class Node {
        String w;
        int v;
        double c;

        Node(String w,int v,double c) {
            this.w = w;
            this.v = v;
            this.c = c;
        }
    }
}