[Java] 백준 - 1916 최소비용 구하기

1916번: 최소비용 구하기

 

정답 코드

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

class Main {
    private static List<List<Node>> adj;
    private static int[] minCost;
    private static boolean[] visited;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        adj = new ArrayList<>(N + 1);

        for (int i = 0; i < N + 1; i++) {
            adj.add(new ArrayList<>());
        }

        minCost = new int[N + 1];
        visited = new boolean[N + 1];

        Arrays.fill(minCost, Integer.MAX_VALUE);

        StringTokenizer st;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            adj.get(start).add(new Node(end, weight));
        }
        st = new StringTokenizer(br.readLine());
        int departure = Integer.parseInt(st.nextToken());
        int destination = Integer.parseInt(st.nextToken());

        minCost[departure] = 0;

        System.out.println(dijkstra(departure, destination));
    }

    private static int dijkstra(int departure, int destination) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(departure, 0));
        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (!visited[cur.next]) {
                visited[cur.next] = true;

                for (Node node : adj.get(cur.next)) {
                    if (!visited[node.next] && minCost[node.next] > cur.weight + node.weight) {
                        minCost[node.next] = cur.weight + node.weight;
                        pq.offer(new Node(node.next, minCost[node.next]));
                    }
                }
            }
        }
        return minCost[destination];
    }

    static class Node implements Comparable<Node> {
        int next;
        int weight;

        public Node(int next, int weight) {
            this.next = next;
            this.weight = weight;
        }

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

필요한 요소

• 인접리스트(혹은 행렬) - adj
• 최소비용 배열: 시작노드에서 특정노드까지 가는데 소요되는 최소 비용 -  minCost
• 방문노드 체크 배열 - visited
• 우선순위 큐 - pq 
• 다음 행선지와 가중치가 필드인 노드 클래스 - Node

 

 

알게된 점

1. 다익스트라는 현재 노드에서 가중치가 가장 낮은 노드 부터 탐색한다. 이를 가능케하기 위해 Node클래스에서 Comparable을 구현하고 우선수위 큐에 Node를 삽입해 구현한다.
2. 이미 방문한 노드를 재방문해서 최소 비용을 계산하지 않는 이유: pq에 의해 가중치가 낮은 순으로 정렬되어서 차례로 탐색하는데, 어떤 노드의 이후 노드가 이전 노드를 탐색했을 때의 가중치 합이 이전 노드의 가중치 합보다 낮을 수가 없기 때문이다.(추정)