[Algo] 백준 11779 최소비용 구하기 2 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/11779

메모리 : 50720KB

시간 : 536ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PrimitiveIterator;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static class Node implements Comparable<Node> {
        int idx, cost;

        Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

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

    static ArrayList<Node>[] graph;
    static int N, M;
    static int[] dist, before;

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        graph = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        StringTokenizer st;
        // 그래프만들기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int idx = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph[v].add(new Node(idx, cost));
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        dijstra(start);
        StringBuilder sb = new StringBuilder();
        sb.append(dist[end]).append("\n");
        Stack<Integer> stack = new Stack<>();
        stack.push(end);
        while (before[end] != 0) {
            stack.push(before[end]);
            end = before[end];
        }
        sb.append(stack.size()).append("\n");
        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(" ");
        }
        System.out.print(sb);
    }

    private static void dijstra(int start) {
        boolean[] check = new boolean[N + 1];
        dist = new int[N + 1];
        before = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            if (!check[now.idx]) {
                check[now.idx] = true;
                for (Node next : graph[now.idx]) {
                    if (!check[next.idx] && dist[next.idx] > now.cost + next.cost) {
                        dist[next.idx] = now.cost + next.cost;
                        before[next.idx] = now.idx;
                        pq.add(new Node(next.idx, dist[next.idx]));
                    }
                }
            }
        }
    }
}

풀이

한 점에서 다른 점까지의 최소비용을 구하는 문제. 바로 다익스트라 이다!

//시작점에서 가장 가까운 노드를 꺼내서
while (!pq.isEmpty()) {
    Node now = pq.poll();
    //방문하지 않았으면 방문해서
    if (!check[now.idx]) {
        check[now.idx] = true;
        for (Node next : graph[now.idx]) {
            //처음 방문하는데, 오름차순 정렬이기 때문에 처음 방문할때가 항상 최소이다.
            if (!check[next.idx] && dist[next.idx] > now.cost + next.cost) {
                //최솟값으로 갱신
                dist[next.idx] = now.cost + next.cost;
                //어디서 왔는지 기록해놓기
                before[next.idx] = now.idx;
                pq.add(new Node(next.idx, dist[next.idx]));
            }
        }
    }
}

이 문제는 또 최소비용이 되는 정점들을 구해야한다. 따라서 before배열에 어떤 노드가 어디로 향하는지 이 끝 노드에서 시작노드까지 before배열을 돌면서 역추적한다. 이를 스택에 넣은다음 꺼내주면 정점리스트를 구할 수 있다.

++ 크루스칼과 다익스트라의 차이

• 다익스트라는 시작점-끝점가지의 최소비용을 구할 수 있다. 우선순위큐를 사용해 O(MlogN)의 시간복잡도로 계산할 수 있다. 음의 가중치는 사용하지 못한다. (음의 가중치는 벨만포드)
• 크루스칼은 최소간선트리이다. 트리 전체를 순회하는 최소비용을 구할 수 있다.