[백준] 1753번 최단경로 (JAVA)

문제

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

1753번: 최단경로

 

설명

주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구해야 한다.
단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력된 간선 정보를 저장할 Edge 클래스를 만들고 리스트를 만들어 연결관계를 저장한다.

시작 정점에서부터 인덱스에 해당하는 정점까지의 최단 거리를 나타내는 minLength[] 배열을 만든다.

음의 가중치가 없는 그래프에서 최단 경로를 구하는 방법으로 다익스트라 알고리즘을 사용할 것이다.

가중치가 작은 간선을 우선으로 하는 우선순위 큐를 만든다.

시작 정점과 가중치를 각각 K와 0으로 하여 우선순위 큐에 삽입한다.

class Edge {
    int dest;
    int cost;

    public Edge(int dest, int cost) {
        this.dest = dest;
        this.cost = cost;
    }

    public int getCost() {
        return cost;
    }
}

PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(Edge::getCost));
pq.offer(new Edge(K, 0));

우선순위 큐가 비어있을 때까지 최단 거리를 갱신한다.

먼저 우선순위 큐에서 하나를 빼내어 해당 dest와 인접한 정점들을 비교한다.

dest에서 다음 목적지로 가는 거리가 현재 최단 거리보다 작다면 최단 거리를 갱신하고 우선순위 큐에 넣는다.

모든 과정이 끝난 후에도 경로가 존재하지 않는 경우에는 "INF"를 출력한다.

void findMinLength() {
    while (!pq.isEmpty()) {
        Edge edge = pq.poll();
        int D = edge.dest;
          
        int len = list.get(D).size();

        // 인접 리스트로 비교
        for (int i = 0; i < len; i++) {
            int nextD = list.get(D).get(i).dest;
            int nextC = list.get(D).get(i).cost;

            // dest에서 다음 목적지로 가는 거리가 현재 계산된 최단 거리보다 작다면
            if (minLength[nextD] > minLength[D] + nextC) {
                // 최단 거리 테이블을 갱신
                minLength[nextD] = minLength[D] + nextC;
                // 우선순위 큐에 넣는다
                pq.offer(new Edge(nextD, minLength[nextD]));
            }
        }
    }

    for (int i = 1; i <= V; i++) {
        if (minLength[i] == Integer.MAX_VALUE)
           System.out.println("INF");
        else
            System.out.println(minLength[i]);
    }
}

 

전체 코드

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

public class Main {

    static int V, E, K;
    static ArrayList<ArrayList<Edge>> list;
    static PriorityQueue<Edge> pq;
    static int[] minLength;

    static class Edge {
        int dest;
        int cost;

        public Edge(int dest, int cost) {
            this.dest = dest;
            this.cost = cost;
        }

        public int getCost() {
            return cost;
        }
    }

    static void findMinLength() {
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int D = edge.dest;
          
            int len = list.get(D).size();

            // 인접 리스트로 비교
            for (int i = 0; i < len; i++) {
                int nextD = list.get(D).get(i).dest;
                int nextC = list.get(D).get(i).cost;

                // dest에서 다음 목적지로 가는 거리가 현재 계산된 최단 거리보다 작다면
                if (minLength[nextD] > minLength[D] + nextC) {
                    // 최단 거리 테이블을 갱신
                    minLength[nextD] = minLength[D] + nextC;
                    // 우선순위 큐에 넣는다
                    pq.offer(new Edge(nextD, minLength[nextD]));
                }
            }
        }

        for (int i = 1; i <= V; i++) {
            if (minLength[i] == Integer.MAX_VALUE)
                System.out.println("INF");
            else
                System.out.println(minLength[i]);
        }
    }

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

        list = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            list.add(new ArrayList<>());
        }

        minLength = new int[V + 1];
        for (int i = 1; i <= V; i++) {
            if (i == K)
                minLength[i] = 0;
            else
                minLength[i] = Integer.MAX_VALUE;
        }

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

            list.get(u).add(new Edge(v, w));
        }

        pq = new PriorityQueue<>(Comparator.comparingInt(Edge::getCost));
        pq.offer(new Edge(K, 0));

        findMinLength();
    }
}