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

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

https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

풀이

최소 비용을 구하면서, 최소 비용 경로까지 함께 구하는 문제였다. 출발 노드가 정해져 있으므로 다익스트라 알고리즘을 사용하여 출발 노드로 부터 모든 노드까지의 최소 비용을 구해주었다. 

 

처음에는 다익스트라 알고리즘 내부에서 우선순위 큐(최소 힙)에 노드를 넣어 주는 것을 최소 비용 경로로 계산해 주었다. 하지만 이는 정답이 아니다. 출발 노드 -> 목적 노드까지는 모든 노드를 거치지 않을 수도 있지만, 다익스트라 알고리즘은 모든 노드를 탐색하기 때문이다.

 

경로를 저장해 주기 위해 새로운 route라는 배열을 생성해 주었다. route의 인덱스가 의미하는 바는 해당 인덱스 번호를 가진 노드 바로 직전에 방문한 노드를 저장하도록 하였다. 다음과 같이 말이다.

route[next.e] = current.e;

 

그리고 다익스트라 탐색을 마친 뒤, end노드 부터 거꾸로 경로를 찾아갔다. route[route[end]]... 이런식으로 반복하도록 while문을 사용하였다. 이전 노드가 더 이상 존재하지 않는다면 0일 것이다. 그러므로 0이 아닐 동안만 반복하도록 해 주었다.

 

거꾸로 경로를 찾아가며 만나는 노드들을 routes라는 list에 저장해 준다. 이 routes list를 통해 최소 비용 경로에 포함 된 도시 개수와 경로를 모두 찾을 수 있다.

 

코드

import java.util.*;
 
public class Main {
    
    static ArrayList<Node>[] list;
    static int n, m, start, end; 
    static int[] dist;
    static int[] route; // 직전 노드 저장
    static boolean[] visited; 
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        
        list = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < m; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            int c = scan.nextInt();
            list[s].add(new Node(e, c));
        }
        
        start = scan.nextInt();
        end = scan.nextInt();
        
        dist = new int[n + 1];
        route = new int[n + 1];
        Arrays.fill(dist, 1000000001);
        visited = new boolean[n + 1];
        dijkstra();
        
        System.out.println(dist[end]);
        
        ArrayList<Integer> routes = new ArrayList<>();
        int current = end;
        while(current != 0) {
            routes.add(current);
            current = route[current];
        }
        System.out.println(routes.size());
        for(int i = routes.size() - 1; i >= 0; i--) {
            System.out.print(routes.get(i) + " ");
        }
    }
    
    public static void dijkstra() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start, 0));
        dist[start] = 0;
        route[start] = 0;
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            if(!visited[current.e]) visited[current.e] = true;
            else continue;
            
            for(int i = 0; i < list[current.e].size(); i++) {
                Node next = list[current.e].get(i);
                if(dist[next.e] > dist[current.e] + next.cost) {
                    dist[next.e] = dist[current.e] + next.cost;
                    q.offer(new Node(next.e, dist[next.e]));
                    route[next.e] = current.e;
                }
            }
        }
    }
    
    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 n) {
            return this.cost - n.cost;
        }
    }
}