[Java]백준 1753 다익스트라

package solving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*
 * [조건]
 * 시간 제한 : 1초 / 메모리 제한 : 256MB
 * V <= 20,000 / E <= 300,000
 * [풀이]
 * 각 정점에서 다른 정점으로의 최솟값을 다익스트라를 통해 구한다.
 * 정점으로부터 최단거리의 간선으로만 이동하기 때문에 O(E * logV) ≈ 1,500,000으로, 모든 간선을 확인하는 것이 가능하다.
 * 탐색하는 간선 개수를 최적화하기 위해 linkedList로 저장한다.(V^2 >> E)
 */
public class bj_1753_다익스트라 {
    static int INF = Integer.MAX_VALUE;
    static int V, E, K;
    static Node[] adj;

    static class Node {
        int v;
        int w;
        Node next;

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

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

        // 간선 리스트 초기화
        adj = new Node[V + 1];
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            adj[from] = new Node(to, w, adj[from]);
        }

        // 다익스트라
        int[] dijkstra = dijkstra();
        for (int i = 1; i <= V; i++) System.out.println(dijkstra[i] == INF? "INF" : dijkstra[i]);
    }

    // 각 목표지점까지의 다익스트라
    private static int[] dijkstra() {
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]); // 가중치의 최솟값 저장
        pq.offer(new int[] {K, 0}); // int[0] : 정점, int[1] : 현재까지의 최단경로
        int[] distance = new int[V + 1]; // 거리 배열 초기화
        Arrays.fill(distance, INF);
        distance[K] = 0;

        while (!pq.isEmpty()) {
            int[] now = pq.poll();
            if (distance[now[0]] < now[1]) continue;  // 현재 거리배열보다 작은값은 사용하지 않음(최적화)
            for (Node n = adj[now[0]]; n != null; n = n.next) {
               int total = now[1] + n.w;  // 이전 최단경로에서 가중치를 더하여 현재 최단경로를 구함
               if (total < distance[n.v]) {
                   distance[n.v] = total;  // 거리배열에 현재까지의 최솟값 저장
                   pq.offer(new int[] {n.v, total});  // 우선순위 큐에 현재 최단경로 추가
               }
            }
        }

        return distance;
    }
}