[BaekJoon] 17835 면접보는 승범이네 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int M;
    static int K;
    static int maxCity = 0;
    static long maxDist = Long.MIN_VALUE;
    static Map<Integer, List<Edge>> edges;
    static int[] interviewRooms;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        K = scanner.nextInt();
        edges = new HashMap<>();
        interviewRooms = new int[K];

        for(int city = 1; city <= N; city++)
            edges.put(city, new ArrayList<>());

        // 주어지는 도로 정보를 해당 방향 그대로가 아닌 반대 방향으로 저장한다
        // 이후에 다익스트라를 통해 최소 거리를 구할 때, 주어진 정보가 면접장 정보이기 때문에 면접장 정보들을 이용해서
        // 면접장에서 도시로 가는 최소 거리를 구할 것이다
        // 이렇게 면접장에서 도시로 가는 최소 거리를 구해서 바로 우리가 원하는 도시에서 면접장까지의 거리를 구하려면
        // 주어진 도로 정보를 반대로 저장해놓고 이 정보를 이용하여 다익스트라를 진행한다면 도시에서 면접장까지의 거리를 구할 수 있다
        for(int edge = 0; edge < M; edge++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int distance = scanner.nextInt();

            edges.get(end).add(new Edge(start, distance));
        }

        for(int idx = 0; idx < K; idx++)
            interviewRooms[idx] = scanner.nextInt();
    }

    static void solution() {
        // 다익스트라를 통해 최소 거리를 구한다
        long[] distances = dijkstra(interviewRooms);
        // 주어진 최소 거리를 이용해 가장 먼 도시와 그 거리를 구한다
        findMaxDistanceCity(distances);

        StringBuilder sb = new StringBuilder();
        sb.append(maxCity).append('\n').append(maxDist);
        System.out.println(sb);
    }

    static void findMaxDistanceCity(long[] distances) {
        for(int city = 1; city <= N; city++) {
            if(distances[city] > maxDist) {
                maxDist = distances[city];
                maxCity = city;
            }
        }
    }

    static long[] dijkstra(int[] start) {
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        long[] distances = new long[N + 1];
        Arrays.fill(distances, Long.MAX_VALUE);

        // 시작시에 모든 면접장 정보를 PriorityQueue에 넣어서 진행한다
        // 한 면접장으로부터 다른 모든 도시로의 거리가 중요한 것이 아니라
        // 모든 면접장에서부터 다른 모든 도시로의 거리가 중요한 것이니 면접장 정보 모두를 시작 정보로 넣고 시작해도 좋다
        // 이를 통해 각 면접장에 대해서 한 번씩 다익스트라를 진행하는 것보다 시간을 줄일 수 있다
        for(int startVertex : start) {
            distances[startVertex] = 0L;
            queue.offer(new Edge(startVertex, 0L));
        }

        while(!queue.isEmpty()) {
            Edge cur = queue.poll();
            if(distances[cur.vertex] < cur.distance)
                continue;

            for(Edge next : edges.get(cur.vertex)) {
                int nextVertex = next.vertex;
                long nextDist = cur.distance + next.distance;
                if(nextDist < distances[nextVertex]) {
                    distances[nextVertex] = nextDist;
                    queue.offer(new Edge(nextVertex, nextDist));
                }
            }
        }

        return distances;
    }

    static class Edge implements Comparable<Edge> {
        int vertex;
        long distance;

        public Edge(int vertex, long distance) {
            this.vertex = vertex;
            this.distance = distance;
        }

        @Override
        public int compareTo(Edge e) {
            if(this.distance < e.distance) return -1;
            else if(this.distance > e.distance) return 1;
            return 0;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}