문제

이해

N개의 도시와 M개의 버스가 있다. 버스는 서로 다른 출발점과 도착점을 입력된 비용으로 간다.

우리가 목표로 하는 출발점과 도착점을 입력받았을 때 버스 비용이 최소일 때의 값을 구하여라.

접근

이전에 풀었던 그래프 문제에 비하면 굉장히 직관적인 문제이다.

N개의 도시는 정점, M개의 버스는 간선으로 치환할 수 있다.

간선은 방향성이 가지며 비용이라는 가중치를 가지고 있다.

이전 최단경로 문제에서 확인했듯이 이 경우 데이크스트라 혹은 벨만포드를 활용하면 된다.

데이크스트라를 통해 특정 출발점에 대한 최소 비용 값을 모두 구한 뒤 도착점에 대한 값만 출력하면 된다.

코드

package java_baekjoon;

import java.io.*;
import java.util.*;

public class prob1916 {
    static class edge implements Comparable<edge> {
        int to;
        int cost;

        public edge(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(edge o) {
            // TODO Auto-generated method stub
            return min_cost[this.to] - min_cost[o.to];
        }
    }

    static int N;
    static int B;
    static ArrayList<edge>[] arr_edge;
    static int[] min_cost;
    static boolean[] visited;

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

        N = Integer.parseInt(br.readLine());
        B = Integer.parseInt(br.readLine());
        arr_edge = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            arr_edge[i] = new ArrayList<>();
        }
        min_cost = new int[N + 1];
        Arrays.fill(min_cost, Integer.MAX_VALUE);
        visited = new boolean[N + 1];

        for (int i = 0; i < B; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            arr_edge[v1].add(new edge(v2, cost));
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int dest = Integer.parseInt(st.nextToken());

        dijkstra(start);

        System.out.println(min_cost[dest]);
    }

    static void dijkstra(int start) {
        PriorityQueue<edge> pq = new PriorityQueue<>();
        pq.add(new edge(start, 0));
        min_cost[start] = 0;

        while (!pq.isEmpty()) {
            edge now = pq.poll();

            if (visited[now.to]) {
                continue;
            }
            visited[now.to] = true;
            
            for (int i = 0; i < arr_edge[now.to].size(); i++) {
                edge next = arr_edge[now.to].get(i);

                int min = min_cost[now.to] + next.cost;
                min_cost[next.to] = Math.min(min, min_cost[next.to]);
                pq.add(next);
            }
        }
    }

}

결과