[Java] 백준 11779번 최소비용 구하기 풀이

✅문제

✅문제 풀이 

어떤 출발 도시에서 도착 도시까지의 최단 비용을 구하고 거쳐가는 경로와 지나는 도시의 개수를 출력하는 문제이다. 경로에 비용이 있기때문에 다익스트라 알고리즘을 사용해야한다.

간단하게 다익스트라 알고리즘을 소개하자면 어떤 정점에서 각 정점까지의 최단거리인 표를 만들고, 정점 마다 각 정점까지 거리를 계산해 그 어떤 정점에서 각 정점까지의 최단 거리를 계속해서 업데이트해 최단 거리를 알아내는 알고리즘이다. 

짧은 예시 하나로 설명하겠습니다.

이러한 그래프가 있다고 예시를 들고, 시작점을 1이라고 하자.

그럼 처음 초기화 된 표는 다음과 같고

정점	1	2	3	4	5
경로값	무한	무한	무한	무한	무한

 

1부터 탐색을 시작하게되면 아래와 같은 표로 값을 넣는다. 정점 5로가는 경로는 현재로서는 아예 모르기때문에 무한이나 Integer.MAX_VALUE로 들어가게 되고 2,3,4는 1과 인접해있기때문에 그 비용이 들어가게된다.

정점	1	2	3	4	5
경로값	0	3	6	7	무한

 

1의 탐색이 끝났으니 1을 탐색 끝으로 체크해놓고 다음 정점 2에서 탐색한다. 

이때 1 -> 3 보다  1 -> 2 -> 3가는 경로의 값이 더 적어서 아래 표가 업데이트 됩니다.

정점	1	2	3	4	5
경로값	0	3	4	7	무한

이러한 방식으로 모든 정점을 돌면서 정점 1에서 각 정점을 가는 최소 비용을 구할 수 있습니다.

여기에 PriorityQueue를 쓰는 이유는 각 정점을 둘러볼떄 최소 비용을 먼저 찾기 때문에 알고리즘 성능을 좀 더 높일 수있습니다. 일반 Queue를 사용하면 비용이 높은데도 먼저 들어왔단 이유로 둘러보지 않아도될 값을 둘러보게되기 때문에 PriorityQueue를 사용합니다.

 

✅Code

package classthree;

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

public class Beak11779 {
    public static class Node implements Comparable<Node>{
        int e;
        int cost;
        public Node(int e, int cost) {
            this.e = e;
            this.cost = cost;
        }
        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
    public static class Matrix {
        List<List<Node>> arrays;
        public Matrix(int size) {
            arrays = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                List<Node> rows = new ArrayList<>();
                arrays.add(rows);
            }
        }
        public void addNode(int from, int to, int cost){
            arrays.get(from).add(new Node(to, cost));
        }
    }

    public static class MatrixService {
        private Matrix matrix;
        private List<Integer> distances;
        private List<Integer> routes;
        private List<Boolean> checks;
        public MatrixService(Matrix matrix) {
            this.matrix = matrix;
            distances = new ArrayList<>(Collections.nCopies(matrix.arrays.size(), Integer.MAX_VALUE));
            routes = new ArrayList<>(Collections.nCopies(matrix.arrays.size(), -1));
            checks = new ArrayList<>(Collections.nCopies(matrix.arrays.size(), false));
        }
        public void findShortestDirection(int from){
            PriorityQueue<Node> queue = new PriorityQueue<>();
            queue.add(new Node(from, 0));
            distances.set(from, 0);
            routes.set(from, from);

            while (!queue.isEmpty()) {
                Node cur = queue.remove();

                if (!checks.get(cur.e)) {
                    checks.set(cur.e, true);
                } else {
                    continue;
                }

                for (Node next : matrix.arrays.get(cur.e)) {
                    if (distances.get(next.e) > distances.get(cur.e) + next.cost) {
                        distances.set(next.e, distances.get(cur.e) + next.cost);
                        queue.add(new Node(next.e, distances.get(next.e)));
                        routes.set(next.e, cur.e);
                    }
                }
            }
        }

        public List<Integer> getShortestPath(int to, int from) {
            List<Integer> path = new ArrayList<>();
            for (int at = to; at != from; at = routes.get(at)) {
                path.add(at);
            }
            path.add(from);
            Collections.reverse(path);
            return path;
        }
    }

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

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        Matrix matrix = new Matrix(n);

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            matrix.addNode(
                    Integer.parseInt(st.nextToken()) - 1,
                    Integer.parseInt(st.nextToken()) - 1,
                    Integer.parseInt(st.nextToken()));

        }
        MatrixService matrixService = new MatrixService(matrix);

        st = new StringTokenizer(br.readLine());
        int from = Integer.parseInt(st.nextToken()) - 1;
        int to = Integer.parseInt(st.nextToken()) - 1;

        matrixService.findShortestDirection(from);

        System.out.println(matrixService.distances.get(to));

        List<Integer> path = matrixService.getShortestPath(to, from);
        System.out.println(path.size());

        for (int num : path) {
            System.out.print(num + 1 + " ");
        }
    }
}