5972 - 택배 배송(G5)

문제

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

다음 지도를 참고하세요.

           [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5] 
                3  

농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

입력

첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.

둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.

출력

첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다.

풀이 및 코드

전형적인 다익스트라 알고리즘 사용 문제.

감을 잡고자 전체적인 이해를 주석으로 작성하였음.

import java.io.*;
import java.util.*;
import java.util.function.Function;
import java.util.function.Supplier;

class Main {
    static List<ArrayList<Edge>> graph;
    static int N, M;

    public static void main(String[] args) throws Exception {
        input();
        solve();
    }

    public static void solve() {
        int dp[] = new int[N]; //각 노드 도착 최소거리
        boolean visit[] = new boolean[N]; //방문 여부
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        PriorityQueue<Edge> pq = new PriorityQueue<>(); //해당 PQ는 Edge Comparable로 인해 항상 최단 경로를 우선해서 꺼냄

        //start : 0 -> end : N;
        dp[0] = 0; //자기자신 거리 0
        pq.add(new Edge(0, 0)); //시작 노드 및 비용

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();  //간선 꺼내옴
            int node = edge.node;   //꺼낸 노드
            if(visit[node]) continue;
            visit[node] = true; //방문 처리 (이미 여기서 최단거리 확정됨)

            ArrayList<Edge> arrayList = graph.get(node); //다음 노드에서 갈 수 있는 간선(다음 목적지)
            for(Edge nextEdge : arrayList) { //간선 순회 (현재 node에서 갈 수 있는 다음 경로)
                //현재 노드(node) -> 다음 노드 비교
                //dp[nextEdge.node] : 다음 node(nextNode)까지 가는데 든 최소 비용 (dp)
                //dp[node] + nextEdge.cost : node까지 오는 최소 비용 + 여기서 다음 node(nextNode)까지 걸리는 비용
                if(dp[nextEdge.node] > dp[node] + nextEdge.cost) {
                    dp[nextEdge.node] = dp[node] + nextEdge.cost; //최소 비용 갱신
                    //경로의 최소 비용이 갱신될 때마다 해당 경로를 큐에 넣어 다음 탐색 대상으로 삼는다.
                    pq.add(new Edge(nextEdge.node, dp[nextEdge.node])); //원래 nextEdge가 아니라 변경된 값으로 큐에 넣는다.
                }
            }
        }

        System.out.println(dp[N - 1]); //N까지의 최단 경로 출력
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        for(int i = 0; i < N; i++) graph.add(new ArrayList<>()); //그래프 초기화
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            int cost = Integer.parseInt(st.nextToken());
            graph.get(start).add(new Edge(end, cost));
            graph.get(end).add(new Edge(start, cost)); //양방향 이동 가능함
        }
    }

}

/**
 * Edge : 간선
 * node : 이 Edge를 통해 다음 노드(중간 경유지)의 인덱스를 의미
 * cost : node를 가는 길에 발생하는 비용
 */
class Edge implements Comparable<Edge> {
    int node;
    int cost;

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

    @Override
    public int compareTo(Edge edge) {
        return this.cost - edge.cost;
    }
}