[백준 Baekjoon] 5972번 택배 배송 - JAVA

백준 Baekjoon 5972번 택배 배송 - JAVA

---

문제 풀이

다익스트라 알고리즘 문제이다. 1번 헛간에서 N번 헛간까지 가는 최소한의 소들을 만나며 지나가는 비용을 찾아 출력하면 된다.

여러 방법으로 다익스트라를 구현할 수 있는데 연결리스트 배열과 우선순위 큐를 사용하여 풀었다.

 

헛간간에 무방향이기 때문에 양방향으로 헛간의 정보를 입력 받는다.
모든 방법을 탐색하는 것이 아닌 우선순위 큐를 사용하여 시간 복잡도를 줄였다.

시작점인 1번 헛간 이외의 헛간은 최대길이로 초기화 하고 이를 비교하며 최소 비용을 갱신하는 방법을 사용하였다.
현재 비용과 새로운 비용을 비교하여 해당 헛간으로 가는 비용이 더 적은 경우에만 큐에 추가하는 방식이다.

boolean배열을 만들어 이미 방문한 헛간은 다시 방문하지 않도록 하여 사이클을 방지한다.

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<Node>[] list = new List[N + 1];
        for (int i = 0; i <= N; i++) {
            list[i] = 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());

            list[A].add(new Node(B, C));
            list[B].add(new Node(A, C));
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] dist = new int[N + 1];
        boolean[] visit = new boolean[N + 1];

        pq.add(new Node(1, 0));
        Arrays.fill(dist, 50_000_001);
        dist[1] = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (visit[cur.dest]) continue;
            visit[cur.dest] = true;

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

        System.out.println(dist[N]);
    }

    public static class Node implements Comparable<Node> {
        int dest;
        int dist;

        public Node(int dest, int dist) {
            this.dest = dest;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return this.dist - o.dist;
        }
    }
}