[Baekjoon] 백준 5972번: 택배 배송 (JAVA)

문제 5972

5972번: 택배 배송

 

[ 풀이 과정 ]

간선에 비용이 있고, 최소 비용을 구하는 문제이므로 다익스트라로 풀 수 있습니다. Node 클래스를 만들어 정점의 값과 비용을 저장하고, ArrayList 배열을 만들어 Node 인스턴스를 저장하여 시작 정점에서 도착 정점까지의 간선 비용을 저장합니다.

최소 비용을 구하기 위해 우선순위 큐를 사용하여 비용이 작은 값부터 방문할 수 있도록 하고, dist[]에 각 정점까지의 최소 비용을 저장해줍니다. 

[ 코드 ]

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

public class Main {
    private static class Node implements Comparable<Node> {
        int n, cost;
        public Node(int n, int cost) {
            this.n = n;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node node) {
            return this.cost - node.cost;
        }
    }
    private static ArrayList<Node>[] list;
    private static boolean[] visit;
    private static int[] dist;

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

        list = new ArrayList[N+1];
        for (int i=1; i<=N; i++) {
            list[i] = new ArrayList<>();
        }
        visit = new boolean[N+1];
        dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        for (int i=1; i<=M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list[a].add(new Node(b, c));
            list[b].add(new Node(a, c));
        }

        dijkstra();
        bw.write(String.valueOf(dist[N]));
        bw.flush();
    }

    private static void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(1, 0));

        dist[1] = 0;
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (visit[cur.n]) continue;
            visit[cur.n] = true;

            for (Node next: list[cur.n]) {
                if (dist[next.n] > dist[cur.n] + next.cost) {
                    dist[next.n] = dist[cur.n] + next.cost;
                    pq.offer(new Node(next.n, dist[next.n]));
                }
            }
        }
    }
}