[JAVA]백준 5972: 택배 배송

백준 5972: 택배 배송

Link: https://www.acmicpc.net/problem/5972

풀이

• 이런 문제를 보면 당연하게 다익스트라를 생각해야 한다!
  • a->b로의 최단 경로를 구하는 문제이면서 가중치가 음수가 아닌 그래프
  • 오랜만에 푸는 다익스트라라 너무 반가웠다는 것은 사족.
• 현서의 위치 1에서 찬홍이의 위치 N까지의 최단 경로를 구해야 한다.
• 양방향 그래프이므로 a->b, b->a를 모두 그래프에 기록해야 한다.

package algorithm2024.sep.day18;
import java.io.*;
import java.util.*;

public class BOJ_5972_택배배송 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static ArrayList<ArrayList<Edge>> adjList = new ArrayList<>();

    static class Edge {
        int node;
        int cost;

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

        @Override
        public String toString() {
            return "Edge{" +
                    "node=" + node +
                    ", cost=" + cost +
                    '}';
        }
    }

    public static void main(String[] args) throws Exception{
//        입력 -> 헛간의 수 N, 길의 수 M
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for(int i = 0;i<=N;i++){
            adjList.add(new ArrayList<>());
        }
//        양방향이므로 인접리스트 양쪽에 추가
        for (int i = 0; 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());
            adjList.get(A).add(new Edge(B, C));
            adjList.get(B).add(new Edge(A, C));
        }

//        다익스트라 알고리즘
        PriorityQueue<Edge> pq = new PriorityQueue<>((o1,o2)->{
            return o1.cost-o2.cost;
        });
        pq.add(new Edge(1, 0));
        int[] dijkstra = new int[N+1];
        for (int i = 0; i <= N; i++) {
            dijkstra[i] = Integer.MAX_VALUE;
        }
        while(!pq.isEmpty()){
            Edge cur = pq.poll();
            for(Edge next : adjList.get(cur.node)){
                int newCost = cur.cost+next.cost;
                if (newCost < dijkstra[next.node]) {
                    dijkstra[next.node] = newCost;
                    pq.add(new Edge(next.node, newCost));
                }
            }
        }
        System.out.println(dijkstra[N]);
    }
}

---

Issue

• 없음.