백준 No.1916 최소비용 구하기 - JAVA

 

문제

 

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다.

우리는 A번째 도시에서 B번쨰 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.

A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

 

 

 

풀이

- dijkstra 알고리즘을 통해 start(시작지점을) 파라미터로 넘겨서 dist 배열을 start에서 시작했을 경우 각 노드에 최단 거리를 구한다. 여기서 버스비용이 가중치이다.

- 그렇기 실행하게 되면 dist는 start에서 모든 인덱스(노드)까지의 최단거리가 될 것이다. 이제 dist에 도착점 인덱스를 출력하면 정답이다.

 

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;

public class Main {
    static class Node{
            int v;
            int cost;
            public Node(int v,int cost){
                    this.v = v;
                    this.cost = cost;
            }
    }

    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static boolean visited[];
    static int dist[];
    static int INF = Integer.MAX_VALUE;

    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());

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        dist = new int[N+1];
        visited = new boolean[N+1];

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

        int u = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        solution(u);
        System.out.println(dist[v]);
    }

    public static void solution(int start){
        Arrays.fill(dist,INF);
        PriorityQueue<Node> queue = new PriorityQueue<>(((o1, o2) -> o1.cost - o2.cost));
        queue.add(new Node(start, 0));
        dist[start] = 0;

        while (!queue.isEmpty()){
            Node now = queue.poll();

            if(!visited[now.v]){
                visited[now.v] = true;
                for(Node next : graph.get(now.v)){
                        if(dist[next.v] > dist[now.v] + next.cost){
                                dist[next.v] = dist[now.v] + next.cost;
                                queue.add(new Node(next.v,dist[next.v]));
                        }
                }
            }
        }
    }
}