[백준] 1753 최단경로 - Graph Theory / Java

• 문제 링크

1753번: 최단경로

 

• 풀이 과정

[백준] 1916 최소비용 구하기 - Graph Theory / Java

위 문제와 유사한 구조의 Dijkstra 알고리즘 문제이다.

 

다만 도착점이 따로 주어지지 않고, 모든 노드까지의 최단 거리값을 구해 각각 정답으로써 출력하고,

값의 변화가 없을 시, 즉 해당 노드로 이동하는 경로가 존재하지 않을 시 "INF" 를 출력한다.

 

추가로 이전에 우선 순위 큐의 매개 변수에 람다식으로 가중치의 정렬기준을 지정한 것과 달리,

compareTo 메소드를 Edge 클래스에 오버라이딩하여 구현 시 메모리와 속도면에서 이점이 있음을 알 수 있었다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int[] dist;
    static List<Edge>[] list;
    static int inf = Integer.MAX_VALUE;

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

        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(br.readLine());

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

        Arrays.fill(dist, inf);

        for (int i = 1; i <= v; i++)
            list[i] = new ArrayList<>();

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            list[src].add(new Edge(dest, weight));
        }

        dijkstra(k);

        for (int i = 1; i <= v; i++) {
            if (dist[i] == inf)
                bw.write("INF\n");
            else
                bw.write(dist[i] + "\n");
        }

        bw.flush();
    }

    private static void dijkstra(int source) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();

        pq.offer(new Edge(source, 0));
        dist[source] = 0;

        while (!pq.isEmpty()) {
            Edge now = pq.poll();

            if (now.weight > dist[now.node])
                continue;

            int src = now.node;
            for (Edge dest : list[src]) {
                if (dist[dest.node] > dist[src] + dest.weight) {
                    dist[dest.node] = dist[src] + dest.weight;

                    pq.offer(new Edge(dest.node, dist[dest.node]));
                }
            }
        }
    }

    private static class Edge implements Comparable<Edge> {
        int node, weight;

        public Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return weight - o.weight;
        }
    }

}