다익스트라를 사용하는 최단거리를 구하는 문제이다.
인접리스트를 사용하여 풀이하였다.

풀이

1. 정점의 개수만큼 비어있는 리스트를 선언한다.
2. 시작 정점으로부터 특정 정점까지의 거리를 저장하는 dist 배열을 선언하고 초기값으로 정수형 최댓값을 넣어준다.
3. 우선 순위 큐를 사용하기 위해 정점 클래스는 Comparable 인터페이스를 구현하여 만든다. 클래스 내부에 compareTo 메서드를 오버라이드한다. 이 메서드를 통해 현재 객체와 비교대상 객체의 순서를 정의한다.
4. 다익스트라 알고리즘을 사용하여 시작정점으로부터 각 정점까지의 최단거리를 저장한 후 출력한다.

코드

package BOJ;

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

public class sol1753 {

    static int v, e, k;
    static List<Node>[] connections;
    static int[] dist;

    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());

        st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());

        connections = new ArrayList[v + 1];
        dist = new int[v + 1];

        for (int i = 0; i <= v; i++) {
            connections[i] = new ArrayList<>();
            dist[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < e; i++) {   // 노드 및 간선의 연결 정보 저장
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            connections[start].add(new Node(end, value));
        }

        StringBuilder sb = new StringBuilder();
        dijkstra(k);

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

        System.out.println(sb);
    }

    public static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[start] = 0;
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node curr = pq.poll();

            // 이미 최단 경로가 확인된 노드는 다시 처리하지 않음
            if (dist[curr.end] < curr.value) continue;

            for (Node node : connections[curr.end]) {
                if (dist[node.end] > curr.value + node.value) {
                    dist[node.end] = curr.value + node.value;
                    pq.add(new Node(node.end, dist[node.end]));
                }
            }
        }
    }

    public static class Node implements Comparable<Node> {
        int end, value;

        public Node(int end, int value) {
            this.end = end;
            this.value = value;
        }

        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    }
}

리뷰

다익스트라 알고리즘에 한번 더 공부하게 되었고, 우선순위 큐의 개념 및 구현에 대해서도 공부하게 되는 문제였다. 한 번 더 풀게 된다면 인접행렬로 구현해봐야겠다.