[1916] 최소비용 구하기

🔗 문제 링크

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

🔍 문제 설명

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.

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

⚠️ 제한사항

• $(1 ≤ N ≤ 1,000), (1 ≤ M ≤ 100,000)$

• 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

• 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

🗝 풀이 (언어 : Java)

다익스트라 알고리즘을 이용해서 푸는 문제이다. 가중치가 존재하는 간선을 가진 그래프를 탐색해서 최소의 비용(최단거리)을 구한다. 이를 위해 우선순위 큐(힙)을 이용한다. 후보를 힙에 넣고 거리가 짧은 순으로 힙에서 정렬되어 나온다. 나온 수로 최소비용인지 체크해서 갱신한다. 여기에 더해서 해당 지점의 간선들과 연결된 지점들의 최소비용도 체크해서 갱신해준다. 주의해야 할 점은 이 로직은 시작점을 정해주고 그 지점을 기준 목표 지점까지의 최단거리이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static class Edge { // ~지점으로 ~만큼 비용
        public int to, weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    static class Info { // ~지점까지 가는 최단거리는 ~이다
        public int idx, dist;

        public Info() {
        }

        public Info(int idx, int dist) {
            this.idx = idx;
            this.dist = dist;
        }
    }

    static int[] dist;
    static ArrayList<Edge>[] edges;

    private static void findMinCost(int n, int start) {
        // 거리배열 초기화를 최대로 해서 최단거리로 갱신되게 한다
        for (int i = 1; i <= n; i++)
            dist[i] = Integer.MAX_VALUE;
        // 거리가 작은 값을 우선적으로 뽑아줄 힙
        PriorityQueue<Info> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.dist)); // 오름차순 정렬
        heap.add(new Info(start, 0)); // 시작점을 힙에 넣기
        dist[start] = 0; // 시작점의 최단거리는 0
        // 다익스트라 알고리즘
        while (!heap.isEmpty()) {
            Info info = heap.poll();
            // 만약 뽑은 거리가 최단 거리가 아니면 스킵, 거리가 같아도 간선은 볼가치가 있으므로 스킵 안함
            if (dist[info.idx] < info.dist)
                continue;
            dist[info.idx] = info.dist; // idx 도시의 최단거리 갱신해주기
            // 간선에 연결된 인접 도시의 최소 비용이 지금 도시까지 비용 + 인접 도시로 가는 간선 비용보다 크면 갱신
            for (Edge edge : edges[info.idx]) {
                if (dist[edge.to] > dist[info.idx] + edge.weight) {
                    dist[edge.to] = dist[info.idx] + edge.weight;
                    heap.add(new Info(edge.to, dist[edge.to])); // 힙에 후보 등록해서 정렬
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()), m = Integer.parseInt(br.readLine());
        dist = new int[n + 1]; // 해당 인덱스 도시까지 가는데 드는 비용을 저장
        edges = new ArrayList[n + 1]; // 해당 인덱스 도시에서 다른 도시로 가는 데 비용이 얼마나 드는지 간선모음
        // 리스트 초기화
        for (int i = 1; i <= n; i++)
            edges[i] = new ArrayList<>();
        // 간선 입력
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            edges[Integer.parseInt(st.nextToken())]
                    .add(new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        br.close();
        int start = Integer.parseInt(st2.nextToken()), goal = Integer.parseInt(st2.nextToken());
        findMinCost(n, start);
        System.out.print(dist[goal]);
    }
}