백준 5972 택배배송 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/5972
  친구에게 택배를 전송해야 하는데 가장 최소 경로로 전달하라.

2. 코드가 나오기까지 🛠️

(1) 시간복잡도 분석 ⏳

3. 코드 🌐

(1) SUDO CODE 💬

1. 입력 받기
2. 1번부터 모든 정점까지의 최소 거리를 찾을 때까지 다익스트라

(2) JAVA CODE ☕

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

public class Main {
    static class Dest{
        int idx;
        int w;

        public Dest(int idx, int w){
            this.idx = idx;
            this.w = w;
        }    }    static int V,E; // 정점, 간선 수
    static ArrayList<ArrayList<Dest>> list = new ArrayList<>();
    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());
        for(int i = 0; i <= V; i++){
            list.add(new ArrayList<>());
        }        for(int i = 0; i < E; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list.get(a).add(new Dest(b,w));
            list.get(b).add(new Dest(a,w));
        }        dist = new int[V+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dijkstra();
        System.out.println(dist[V]);
    }
    public static void dijkstra() {
        PriorityQueue<Dest> pq = new PriorityQueue<>((a,b) -> (a.w - b.w));
        pq.add(new Dest(1,0));
        dist[1] = 0;

        while (!pq.isEmpty()){
            Dest now = pq.poll();
            if(dist[now.idx] < now.w) continue; // 현재 갱신된 값보다 큰 값은 볼 필요가 없다.
            for(int i = 0; i < list.get(now.idx).size(); i++){
                Dest next = list.get(now.idx).get(i);
                if(dist[next.idx] > dist[now.idx] + next.w){
                    dist[next.idx] = dist[now.idx] + next.w;
                    pq.add(new Dest(next.idx, dist[next.idx]));
                }
            }
        }
    }
}

4. 트러블 슈팅 or 배운 점📝

• 없음