[백준]5972: 택배 배송 - JAVA

[백준]5972: 택배 배송

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

5972번: 택배 배송

풀이

출발지 헛간에서 목적지 헛간으로 가는 최소 거리를 찾는 문제로 다익스트라 알고리즘을 활용하여 풀었다. 다익스트라를 사용하여 출발지에서 다른 모든 헛간으로 가는 최소 거기를 찾아준 다음, 목적지까지의 거리를 반환해 주었다.

 

헛간 사이에는 방향성이 없으므로 헛간간의 거리를 입력받을때, 입력받는 두 개의 헛간에 모두 정보를 입력해 주었다. 또한 dist의 default값은 입력 받을 수 있는 경로 개수의 최대값(50000)과 한 번에 입력 가능한 cost의 최대값(1000)을 곱한 수를 최소로 하는 50000001으로 설정해 주었다.

 

그리고 다익스트라 알고리즘을 쓰면 답이 나옹당. 

코드

import java.util.*;
 
public class Main {
    
    static int n, m;
    static int[] dist;
    static ArrayList<Node>[] list;
    static boolean[] visited;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
 
        list = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < m; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            int cost = scan.nextInt();
            list[s].add(new Node(e, cost));
            list[e].add(new Node(s, cost));
        }
 
        visited = new boolean[n + 1];
        dist = new int[n + 1];
        Arrays.fill(dist, 50000001); //50000 * 1000 + 1
        dijkstra();
        System.out.println(dist[n]); //목적지는 n
    }
 
    public static void dijkstra() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        dist[1] = 0; //시작 지점은 1
        q.offer(new Node(1, 0));
 
        while(!q.isEmpty()) {
            Node current = q.poll();
 
            if(!visited[current.d]) visited[current.d] = true;
            else continue;
 
            for(int i = 0; i < list[current.d].size(); i++) {
                Node next = list[current.d].get(i);
                if(dist[next.d] > dist[current.d] + next.cost) {
                    dist[next.d] = dist[current.d] + next.cost;
                    q.offer(new Node(next.d, dist[next.d]));
                }
            }
        }
    }
 
    public static class Node implements Comparable<Node> {
        int d;
        int cost;
 
        public Node(int d, int cost) {
            this.d = d;
            this.cost = cost;
        }
 
        @Override
        public int compareTo(Node n) {
            return this.cost - n.cost;
        }
    }
}