[백준] 17835번 - 면접보는 승범이네 [Java]

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

 

[백준] 17835번 - 면접보는 승범이네 [Java]

[백준] 17835번 - 면접보는 승범이네 [Java]

[백준] 17835번 - 면접보는 승범이네 [Java]

---

1.  아이디어

 

각 도시에서 면접장까지의 거리를 구하는 방식으로는 시간초과가 발생했다. 이를 해결하기 위해 면접장에서 도시까지의 거리를 구하는 방식으로 다익스트라 알고리즘을 활용했다.

---

2. 문제풀이

 

면접장으로 주어진 모든 장소를 다익스트라 알고리즘의 출발점으로 설정했고 계산 후 거리 배열에서 가장 먼 도시의 번호와 거리를 구해서 반환하는 방식으로 구현했다. 거리 배열을 최댓값으로 초기화할 때 int형 최대 크기보다 크게 설정해야 함에 주의해야 한다.

---

3. 코드

 

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

public class Main {

    private static class Node implements Comparable<Node> {
        int v;
        long w;

        public Node(int v, long w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Node o) {
            return Long.compare(this.w, o.w);
        }
    }

    private static final long INF = 1_000_000_000_000L;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        List<List<Node>> adjReverse = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adjReverse.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            adjReverse.get(v).add(new Node(u, c));
        }

        PriorityQueue<Node> input = new PriorityQueue<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            input.add(new Node(Integer.parseInt(st.nextToken()), 0));
        }

        long[] result = dijkstra(input, N, adjReverse);

        System.out.println(result[0]);
        System.out.println(result[1]);
    }

    private static long[] dijkstra(PriorityQueue<Node> start, int N, List<List<Node>> adj) {
        PriorityQueue<Node> pq = new PriorityQueue<>(start);

        boolean[] visited = new boolean[1 + N];

        long[] dist = new long[1 + N];
        Arrays.fill(dist, INF);
        for (Node node : start) {
            dist[node.v] = 0;
        }

        while (!pq.isEmpty()) {
            Node node = pq.remove();

            if (visited[node.v]) continue;
            visited[node.v] = true;

            for (Node next : adj.get(node.v)) {
                if (visited[next.v]) continue;

                if (dist[next.v] > dist[node.v] + next.w) {
                    dist[next.v] = dist[node.v] + next.w;
                    pq.add(new Node(next.v, dist[next.v]));
                }
            }
        }

        long maxNum = 0;
        long max = Long.MIN_VALUE;
        for (int i = 1; i <= N; i++) {
            if (dist[i] == 0) continue;

            if (dist[i] > max) {
                maxNum = i;
                max = dist[i];
            }
        }

        return new long[]{maxNum, max};
    }

}

---

4. 후기