[Java] 백준 30974 What's your ETA?

문제

진주 나들이를 온 보선이는 버스를 타고 미리 예약해놓은 진양호 전망대에 가기 위해 가까운 버스 정류장에 도착했다. 그런데 이상하게 버스정보안내단말기에 단 한 대의 도착 정보도 표시되지 않았다. 당황한 보선이가 여기저기 알아보던 도중, 보선이의 대학 동기인 준희로부터 문자 한 통이 왔다.

맛이 어때?

 

알고 보니 이는 준희가 한 짓이었다. 대학생 때 국밥 마니아 보선이 때문에 매일 국밥만 먹게 되었던 리조또 마니아 준희는 지금까지 앙심을 품고 있었다. 마침 준희는 보선이가 진주에 놀러 왔다는 사실을 알게 되었고, 천재적인 해킹 실력을 발휘해 버스정보시스템을 해킹하여 시내버스가 다니지 못하게 만들었던 것이다.

하지만, 진주에는 Super Bus라는 재난 대비 버스가 있었다. 진주시는 버스정보시스템이 해킹된 지금의 상황이 사실상 재난에 준한다고 판단하여 Super Bus의 운행을 시작했다. 또한, Super Bus가 원활하게 운행되기 위해서 다른 교통수단은 전부 이용할 수 없게 되었다.

진주에는 버스 정류장이 N개가 있고 1번부터 차례대로 번호가 부여되어 있다. 그리고 서로 다른 두 버스 정류장 사이를 잇고 Super Bus를 타고 지나가는 데 소요되는 시간이 정해져 있는 M개의 양방향 도로가 있으며, 임의의 두 버스 정류장 사이에 도로가 두 개 이상 존재할 수 있다. 또한, 각 버스 정류장에는 5 000 000 이하의 양의 정수인 재난 코드가 부여되어 있으며, Super Bus는 재난 코드의 합이 소수인 두 버스 정류장 사이를 잇는 도로에서만 운행된다. 이 문제에서 소수란 1과 자기 자신 외의 약수를 갖지 않는 2 이상의 정수를 뜻한다.

보선이는 진주에서 많은 시간을 보냈기 때문에 N개의 버스 정류장의 재난 코드와 그 사이를 잇는 M개의 양방향 도로를 전부 꿰고 있다. 이 지식을 활용해 보선이는 진양호 전망대에 도착하는 시간을 미리 계산해 보고 예약 시간에 늦을 것 같으면 진양호 전망대에 전화를 걸어 그 사실을 알리고자 한다. 보선이가 출발하는 곳은 1번 버스 정류장이고 진양호 전망대가 있는 곳은 N번 버스 정류장이다. 또한, 모든 버스 정류장은 서로 먼 거리에 있기 때문에 Super Bus로만 이동이 가능하다. 그리고 버스 정류장에 도착하면 원하는 Super Bus를 바로 탈 수 있으며, 승하차에 필요한 시간은 없다고 가정하자. 이러한 조건하에 보선이가 진양호 전망대가 있는 N번 버스 정류장에 가장 빨리 도착할 때의 소요되는 시간을 알아보자.

 

입력

첫 번째 줄에는 버스 정류장의 개수 N과 임의의 두 버스 정류장 사이를 잇는 양방향 도로의 개수 M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 400\,000; 1 ≤ M ≤ 1\,000\,000)

두 번째 줄에는 각 버스 정류장의 재난 코드 D_1, …D_N이 공백으로 구분되어 주어진다. (1 ≤ D_i ≤ 5\,000\,000)

세 번째 줄부터 M개의 줄에 걸쳐 각 양방향 도로의 정보 u_i, v_i, w_i가 공백으로 구분되어 주어진다. 이는 u_i번 버스 정류장과 v_i번 버스 정류장 사이를 잇고 Super Bus를 타고 지나가는 데 소요되는 시간은 w_i인 i번째 양방향 도로를 뜻한다. (1 ≤ u_i < v_i ≤ N; 1 ≤ w_i ≤ 400\,000)

입력으로 주어지는 모든 수는 정수이다.

 

출력

첫 번째 줄에 '진양호 전망대'에 가장 빨리 도착할 때의 소요되는 시간을 출력한다. 만약 '진양호 전망대'에 도착하지 못한다면 Now where are you?를 출력한다.

 

문제 링크 : What's your ETA?

---

설명

처음에 BFS로 풀면 풀릴 것 같아서 열심히 BFS로 짜본 코드...(이 코드 참고하지 마세요. 예제는 맞지만 틀린 코드입니다.)

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

public class Main {
    static int[] code = new int[5_000_001];
    static List<Edge>[] list;
    static boolean[] visited, prime;
    static int time, n, m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i<=n;i++){
            code[i] = Integer.parseInt(st.nextToken());
        }
        prime = new boolean[5_000_001];
        Arrays.fill(prime, true);
        for (int i = 2; i<=Math.sqrt(5000000);i++){
            if (!prime[i]) {
                continue;
            }
            for (int j = i + i; j <= 5000000; j += i) {
                prime[j] = false;
            }
        }
        list = new List[n + 1];
        visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++){
            list[i] = new ArrayList<>();
        }
        // 리스트에 시작 노드 + 도착 노드 + 가중치 저장
        for (int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()); int e = Integer.parseInt(st.nextToken());
            int plus = Integer.parseInt(st.nextToken());
            list[s].add(new Edge(e, plus));
            list[e].add(new Edge(s, plus));
        }
        // 시작 버정부터 탐색
        bfs(1);

        if (!visited[n]) System.out.println("Now where are you?");
        else System.out.println(time);

    }
    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;

        while (!q.isEmpty()){
            int now = q.poll();
            for (Edge i : list[now]) {
                int e = i.node;
                int p = i.plus;
                if (!visited[e] && prime[code[now] + code[e]]){
                    time += p;
                    visited[e] = true;
                    q.add(e);
                }
            }
        }
    }
static class Edge{
        int node;
        int plus;

    public Edge(int node, int plus) {
        this.node = node;
        this.plus = plus;
    }
}}

 

해당 코드를 다 입력하고 예제에는 없는 다른 예외 케이스를 이거저거 생각하던 중 이 코드는 정말 예제에서만 돌아가는 것을 알았다...일단 시간이 제대로 저장이 안되고, 애초에 이 문제는 다익스트라 알고리즘을 통해 해결해야하는데 BFS로 풀었으니....핳

 

처음에 소수 배열을 500만으로 잡았던 건 계산을 잘 못 했다.

최대 500만까지 가능하고 두 재난코드의 합을 확인해야하니 최대 1000만으로 값을 잡는게 맞다.

 

에라토스테네스이 체를 이용해서 미리 소수를 다 구해준 다음 재난 코드의 합을 통해 소수가 아닌 버스정류장은 리스트에 넣지 않고 넘겼다. 덕분에 밑에서 조건문을 이용하여 거르지 않아도 됨.

 

그리고 현재 저장된 값보다 작지 않으면 그냥 저장하지 않고 넘겼다. 

 

이렇게 하면 정답이 나오게 된다.

 

처음에 코드를 제출했는데 틀렸습니다가 나와서 리얼 당황...

아무리 봐도 틀린게 없는데 후에 보니 time을 long으로 잡아놓고 Integer.MAX_VALUE로 비교하고 있었던 것...

코드를 잘 보자.

 

코드

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

public class Main {
    static int[] code = new int[400_001];   // 재난 코드 저장
    static ArrayList<Edge>[] list;   // 연결 노드, 시간 저장
    static boolean[] prime = new boolean[10_000_001];   // 소수 판별
    static long[] time;     // 최소 시간 저장
    static int n, m;    // 노드, 도로 개수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i<=n;i++){
            code[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.fill(prime, true);
        for (int i = 2; i<=Math.sqrt(10000000);i++){
            if (!prime[i]) {
                continue;
            }
            for (int j = i * i; j <= 10000000; j += i) {
                prime[j] = false;
            }
        }
        list = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) list[i] = new ArrayList<>();

        time = new long[n + 1];

        for (int i = 0; i <= n;i++) time[i] = Long.MAX_VALUE;

        // 리스트에 시작 노드 + 도착 노드 + 가중치 저장
        for (int i = 1; i <= m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()); int e = Integer.parseInt(st.nextToken());
            int plus = Integer.parseInt(st.nextToken());

            if (!prime[code[s] + code[e]]) continue;    // 소수가 아니라면 저장하지 않고 넘어감

            list[s].add(new Edge(e, plus));     // 시작 노드 위치에 끝 노드, 시간 저장
            list[e].add(new Edge(s, plus));     // 끝 노드 위치에 시작노드, 시간 저장
        }
        // 시작 버정
        dijkstra(1);

        System.out.println((time[n] == Long.MAX_VALUE) ? "Now where are you?" : time[n]);

    }
    static void dijkstra(int start) {
        PriorityQueue<Edge> q = new PriorityQueue<>();
        time[start] = 0;
        q.offer(new Edge(start, 0));

        while (!q.isEmpty()){
            Edge now = q.poll();
            if (time[now.node] < now.plus) continue;

            for (Edge i : list[now.node]) {
                int e = i.node;
                long p = i.plus;

                if (now.plus + p < time[e]) {
                    time[e] = now.plus + p;
                    q.offer(new Edge(e, time[e]));
                }
            }
        }
    }
    static class Edge implements Comparable<Edge>{
        int node;
        long plus;

        public Edge(int node, long plus) {
            this.node = node;
            this.plus = plus;
        }

        @Override
        public int compareTo(Edge o) {
            return Long.compare(plus, o.plus);
        }
    }}