[백준/JAVA] BOJ 11779 - 최소비용 구하기 2

나는 다익스트라가 좋아
문제 편식 그만해야 하는디...

👀 문제

11779번: 최소비용 구하기 2 ✨ 골드 3

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

예제 입력

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

예제 출력

4
3
1 3 5

🔑 키포인트

그래프 이론 다익스트라 역추적

✍️ 코드

📍 다익스트라를 이용해서 최소 비용을 구해 주고, 해당 노드 방문하기 전 노드 인덱스를 담는 배열을 만들어 저장해 경로를 출력해 주면 된다.
💡 나를 방문하기 전 위치가 배열에 담기기 때문에 경로를 거꾸로 거슬러 올라가야 함. ➡️ 스택 사용

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

public class BOJ11779_최소비용구하기2 {
    static class Node implements Comparable<Node> {
        int idx, d;

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

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

    static int n, m, s, e;
    static ArrayList<ArrayList<Node>> graph;
    static boolean[] visited;
    static int[] dist;
    static int[] root;
    static PriorityQueue<Node> q;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        visited = new boolean[n + 1];
        dist = new int[n + 1];
        root = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        graph = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            graph.add(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 d = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Node(b, d));
        }

        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        dist[s] = 0;
        q = new PriorityQueue<>();
        q.offer(new Node(s, 0));
        search();

        sb = new StringBuilder();
        sb.append(dist[e] + "\n");
        rootCheck(root);
        System.out.println(sb.toString());
    }

    static void search() {
        while (!q.isEmpty()) {
            Node now = q.poll();
            visited[now.idx] = true;
            if (now.idx == e) {
                break;
            }
            for (Node next : graph.get(now.idx)) {
                if (!visited[next.idx] && dist[next.idx] > dist[now.idx] + next.d) {
                    root[next.idx] = now.idx;
                    dist[next.idx] = dist[now.idx] + next.d;
                    q.offer(new Node(next.idx, dist[next.idx]));
                }
            }
        }
    }

    static void rootCheck(int[] root) {
        Stack<Integer> stack = new Stack<>();

        int prev = e;
        stack.add(prev);
        while (prev != s) {
            stack.add(root[prev]);
            prev = root[prev];
        }

        sb.append(stack.size() + "\n");
        while (!stack.isEmpty()) {
            sb.append(stack.pop() + " ");
        }
    }
}