[Java] 11779번. 최소비용 구하기 2 (#다익스트라 알고리즘)

문항출처 : https://www.acmicpc.net/problem/11779

기존 문항의 업그레이드 버전 문항이다.
(참고 : 1916번. 최소비용 구하기 https://velog.io/@osh8242/BOJ-1916)
그래프에서 두 노드 간의 최소비용 경로를 찾아 최소비용만을 출력하는 것이 기존문항이었는데
이 문항에서는 최소비용 뿐만 아니라
거쳐가는 노드 경로까지 출력해야한다.
기존 문항을 풀었다면 간단하다..
int 값만을 비용배열로 저장하는 것이 아니라 class 객체형태를 정의하고
int값과 경로내역을 객체(History)에 담아주면 된다.

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

class Main {
	
    //Node 정보를 담기위한 class
    //Node 객체간 비교를 위한 Interface인 Comparable 상속.
    static class Node implements Comparable<Node>{
    	//해당 노드 index와 해당 노드로 이동시 드는 비용 price
        public int index;
        public int price;
        public Node(int index, int price){
            this.index = index;
            this.price = price;
        }
        
        //노드 비교를 위한 compareTo() 오버라이딩
        //리턴값이 음수이면 현재 노드가 우선
        //리턴값이 양수이면 비교대상 노드가 우선
        @Override
        public int compareTo(Node o) {
            return this.price - o.price;
        }
    }
    
    //총비용과 경로내역을 담기위한 class History
    static class History{
    	//총비용 totalPrice, 경로내역을 담는 ArrayList<> path
        public int totalPrice;
        public ArrayList<Integer> path;
        public History(){
            this.totalPrice = Integer.MAX_VALUE;
            this.path = new ArrayList<>();
        }
        
        //경로에 새로운 index가 추가될 때, History를 갱신하는 함수
        public void updateHistory(Node newNode, History prevHistory){
            this.totalPrice = newNode.price + prevHistory.totalPrice;
            this.path = (ArrayList<Integer>) prevHistory.path.clone();
            this.path.add(newNode.index);
        }

    }
	
    //노드의 갯수 n, 노드간의 경로를 담는 ArrayList<> paths
    static int n;
    static ArrayList<Node>[] paths;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //노드 갯수 n을 입력받기
        n = Integer.parseInt(br.readLine());
        
        //n개의 노드 각각에서부터 이동할 수 있는 경로정보를 담을 수 있게 ArrayList<> 배열 생성
        paths = new ArrayList[n+1];
        for(int i = 1 ; i <= n ; i++) paths[i] = new ArrayList<>();
		
        //경로 정보 입력받기
        int m = Integer.parseInt(br.readLine());
        while(m-->0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            paths[start].add(new Node(end, price));
        }
        
        //시작노드와 종료노드 입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int startIndex = Integer.parseInt(st.nextToken());
        int endIndex = Integer.parseInt(st.nextToken());

		//다익스트라 함수로 정답찾기
        History answer = dijkstra(startIndex, endIndex);
        
        //정답출력
        StringBuilder sb = new StringBuilder();
        sb.append(answer.totalPrice+"\n");
        sb.append(answer.path.size()+"\n");
        for(int index : answer.path){
            sb.append(index+" ");
        }
        System.out.println(sb);

    }
	
    //다익스트라 알고리즘 함수    
    static History dijkstra(int startIndex, int endIndex){
    	//우선순위큐와 최소비용 경로정보를 담는 Histtory 배열 생성
        PriorityQueue<Node> pq = new PriorityQueue<>();
        History[] histories = new History[n+1];
        for(int i = 1 ; i <= n ; i++) histories[i] = new History();
		
        //시작노드 집어넣고 첫 history 설정해주기
        pq.add(new Node(startIndex, 0));
        histories[startIndex].totalPrice = 0;
        histories[startIndex].path.add(startIndex);
		
        //큐가 비지 않으면 계속 반복
        while(!pq.isEmpty()){
        	//현재 탐색노드 node
            Node node = pq.poll();
            int currentIndex = node.index;
            int currentPrice = node.price;
			
            //만약 현재노드로의 비용이 History에 기록된 비용보다 크다면
            //탐색의 의미가 없으므로 continue;
            if(currentPrice > histories[currentIndex].totalPrice) continue;
			
            //현재 노드와 연결된 경로정보들을 가져옴
            ArrayList<Node> cNodes = paths[currentIndex];
            for(Node cNode : cNodes){            	
                int newIndex = cNode.index;
                int newPrice = histories[currentIndex].totalPrice + cNode.price;
                //현재 노드를 거쳐 cNode로 이동하는 것이 기존 기록보다 더 적은 비용이라면
                if(histories[newIndex].totalPrice > newPrice){
                	//기록 갱신 후 새롭게 큐에 cNode를 담기
                    histories[newIndex].updateHistory(cNode, histories[currentIndex]);
                    pq.add(new Node(newIndex, newPrice));
                }
            }
        }
        
		//종료노드의 기록 History 객체를 반환
        return histories[endIndex];
    }


}