BOJ 1753 최단경로 [Java]

BOJ 1753 최단경로

1. 문제 링크

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

2. 문제 해설

다익스트라 알고리즘을 이용하는 기본 문제이다. 다익스트라 알고리즘 구현을 연습하기에 좋았다.
코드 구현에 대한 설명은 아래 다익스트라 알고리즘에 대해 써놓은 글을 참고해보자.
[최단 거리 알고리즘 - 다익스트라 [Java]]

3. 코드 보기

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

public class Main {
    static class Node implements Comparable<Node> {
        int vertex;
        int distance;

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

        @Override
        public int compareTo(Node node) {
            return this.distance <= node.distance ? -1 : 1;
        }
    }

    static int v, e, start;
    static int[] dis;
    static ArrayList<ArrayList<Node>> arr = new ArrayList<ArrayList<Node>>();

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

        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(br.readLine());
        dis = new int[v + 1];

        for (int i = 0; i < v + 1; i++) {
            arr.add(new ArrayList<>());
        }

        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 distance = Integer.parseInt(st.nextToken());

            arr.get(from).add(new Node(to, distance)); // arr에 들어가는 Node 원소는 다음 정점과 간선 정보를 담는다.
        }

        Arrays.fill(dis, Integer.MAX_VALUE);
        solve(start);

        for (int i = 1; i < v + 1; i++) {
            if (dis[i] == Integer.MAX_VALUE) {
                sb.append("INF" + "\n");
            } else {
                sb.append(dis[i] + "\n");
            }
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }

    static void solve(int x) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dis[x] = 0;
        pq.add(new Node(x, dis[x])); // pq에 들어가는 Node 원소는 정점과 시작점부터 그 정점까지의 최단 거리를 담는다.

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            int curVertex = cur.vertex;
            int xToCurDistance = cur.distance;

            if (xToCurDistance > dis[curVertex]) {
                continue;
            }

            for (Node child : arr.get(curVertex)) {
                int nxtVertex = child.vertex;
                int curToNxtDistance = child.distance;

                if (xToCurDistance + curToNxtDistance < dis[nxtVertex]) {
                    dis[nxtVertex] = xToCurDistance + curToNxtDistance;
                    pq.add(new Node(nxtVertex, dis[nxtVertex]));
                }
            }
        }
    }
}