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

문제링크 : https://www.acmicpc.net/problem/1916

#다익스트라 알고리즘
가중치 있는 그래프에서 어떤 두 노드 간의 경로 중 최소비용(or 최대비용) 경로를 찾는 알고리즘이다.
우선순위 큐를 이용해 탐색할 경우 시간복잡도는 O(nlogN)이다.

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

class Main {
	// 우선순위 큐를 이용할 때 객체들 간의 우선순위를 정하기 위해 인터페이스 Comparable<T> 를 상속
    static class Node implements Comparable<Node> {
        public int index;
        public int price;
		
        //해당 노드번호(index)와 이 노드로 이동하기 위한 비용(price) 정보를 갖는 객체(Node)
        public Node(int index, int price) {
            this.index = index;
            this.price = price;
        }
		
        //객체 간의 우선순위를 비교하기 위한 함수 compareTo() 오버라이딩
        //리턴값이 음수라면 현재 노드가 우선, 양수라면 비교대상 노드가 우선
        //여기서는 price(비용값)이 작은 것을 우선
        @Override
        public int compareTo(Node o) {
            return this.price - o.price;
        }
    }

    static ArrayList<Node>[] paths;
    static int[] prices;
    static int n, startNode, endNode;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //노드의 개수 n
        n = Integer.parseInt(br.readLine());
        
        //경로정보를 담는 배열 paths
        paths = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) paths[i] = new ArrayList<>();
        
        //비용배열 prices[]
        prices = new int[n + 1];
        Arrays.fill(prices, Integer.MAX_VALUE);
		
        //경로의 개수 m
        int m = Integer.parseInt(br.readLine());
        //경로정보 입력받기
        for (int i = 0; i < m; i++) {
            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());        
        startNode = Integer.parseInt(st.nextToken());
        endNode = Integer.parseInt(st.nextToken());
		
        //다익스트라 알고리즘 수행
        dijkstra(startNode);
		
        //정답 출력
        System.out.println(prices[endNode]);
    }

    static void dijkstra(int startNode) {
    
    	//노드를 담는 우선순위큐
        PriorityQueue<Node> pq = new PriorityQueue<>();
        
        //시작노드 입력
        pq.add(new Node(startNode, 0));
        prices[startNode] = 0;
		
        //우선순위큐에 더이상 수행할 노드가 없을 때까지 반복
        while (!pq.isEmpty()) {        	
            Node node = pq.poll();
            //현재 index와 출발index에서부터 현재index까지의 비용
            int currentIndex = node.index;
            int currentPrice = node.price;
			
            //현재 index로의 비용이 최소비용을 기록하고 있던 비용배열의 값보다 크면
            //탐색의 의미가 없으므로 continue;
            if (currentPrice > prices[currentIndex]) continue;
			
            //현재index와 연결된 index들의 정보(cNodes)를 가져옴
            ArrayList<Node> cNodes = paths[currentIndex];
                        
            for (Node cNode : cNodes) {
                int newIndex = cNode.index;
                int newPrice = currentPrice + cNode.price;
                
                //만약 현재index를 거쳐 cNode의 index로 가는 비용이 
                //비용배열에 기록된 비용값보다 더 작다면
                //더 적은 비용경로를 찾은 것이므로 비용배열값을 갱신하고
                //해당 index에서 추가탐색하기 위해 우선순위큐에 해당 노드를 추가함
                if (newPrice < prices[newIndex]) {
                    prices[newIndex] = newPrice;
                    pq.add(new Node(newIndex, newPrice));
                }
            }
        }
    }
}