[BOJ/GoldIII] 11779. 최소 비용 구하기 2 - JAVA 자바

11779번: 최소비용 구하기 2

• 532ms
• 다익스트라

특정노드에서 다른노드까지의 최소 비용을 구하는 문제로 다익스트라 알고리즘을 사용했다. 단, 이 문제에서는 최소 비용뿐만 아니라 출발노드에서 도착노드까지의 최단 경로에 포함되는 노드 또한 출력해줘야 한다.

 

다익스트라는 많이 해봐서 빠르게 최소비용을 구할 수 있었지만 최단 경로에 포함되어 있는 노드를 찾는 데 어려움이 있었다. 다익스트라 알고리즘에 이전의 노드를 저장해주는 코드를 추가한 후, 경로를 역추적하며 해결할 수 있었다.

 

경로를 역추적을 위해 현재 노드 기준으로 방문한 이전 노드를 저장해주는 pre 배열을 선언해주었다. 이 후 pre 배열의 도착 노드인 b 부터 stack을 통해 출력해주면 출발노드에서 도착노드까지 경로를 알 수 있다.

import java.io.*;
import java.util.*;

public class Main {
    static int n, m, a, b;
    static int count = 1;
    static int[] d, pre;
    static List<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();

    static class Node implements Comparable<Node> {
        int index;
        int distance;

        public Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }

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

    }

    public static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        d[start] = 0;
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int now = node.index;
            int dist = node.distance;

            if (dist > d[now])
                continue;

            // now와 인접한 노드 중 출발노드에서 now를 거쳐가는 것이 더 빠른경우
            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).dist;
                if (cost < d[graph.get(now).get(i).index]) {
                    d[graph.get(now).get(i).index] = cost;
                    pq.offer(new Node(graph.get(now).get(i).index, cost));
                    pre[graph.get(now).get(i).index] = now;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        d = new int[n + 1];
        pre = new int[n + 1]; // 이전 도시가 무엇인지 저장
        Arrays.fill(d, Integer.MAX_VALUE);
        for (int i = 0; i <= n; i++)
            graph.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            graph.get(Integer.parseInt(st.nextToken()))
                    .add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        dijkstra(a);

        sb.append(d[b]).append('\n');

        Stack<Integer> stack = new Stack<>();
        stack.push(b);
        while (pre[b] != 0) {
            count++;
            stack.push(pre[b]);
            b = pre[b];
        }

        sb.append(count).append('\n');
        while (!stack.isEmpty())
            sb.append(stack.pop()).append(' ');

        System.out.println(sb);
    }
}

 

해당 문제는 스페셜저지 문제로 첫 번째 예제 출력이 다음과 같이 나와도 Success 이다. (몰라서 제출안하고 왜 틀린지 계속 찾은 사람 나..)

4
3
1 4 5