[백준] 1916번 - 최소비용 구하기 (Gold 5)

문제 링크

[백준] 1916번 - 최소비용 구하기 (Gold 5)

문제 설명

도시의 개수와 버스의 개수 및 각 버스의 정보가 주어진다.
버스의 정보는 출발 도시의 번호, 도착 도시의 번호, 버스의 비용으로 이루어져 있다.
도시는 1,000개 이하이며, 버스의 개수는 100,000개 이하, 버스 비용은 0 이상 100,000 이하의 정수이다.
출발 도시와 도착 도시가 주어졌을 때, 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
항상 이동 가능한 입력만 주어진다고 가정한다.

정답 코드 및 설명

전형적인 다익스트라 알고리즘 문제이다.
두 도시를 잇는 버스가 여러개일 수도 있는데, 간결한 처리를 위해 입력 과정에서 출발지와 도착지가 같다면 가장 비용이 저렴한 버스만을 남겼다.
버스 비용이 0일 수도 있으므로, 그래프를 인접 행렬로 저장할거라면 끊어진 것과 0을 구분해줘야 한다.
아래 코드에서는 끊어진 것은 null로, 버스 비용이 0인 것은 0으로 처리하였다.

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ1916 {
    final int INF = Integer.MAX_VALUE;
    int n;
    Integer[][] bus;
    int start, end;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        bus = new Integer[n][n];
        StringTokenizer st;
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int busStart = Integer.parseInt(st.nextToken()) - 1;
            int busEnd = Integer.parseInt(st.nextToken()) - 1;
            int busCost = Integer.parseInt(st.nextToken());
            if (bus[busStart][busEnd] == null || busCost < bus[busStart][busEnd])
                bus[busStart][busEnd] = busCost;
        }
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken()) - 1;
        end = Integer.parseInt(st.nextToken()) - 1;
    }

    // 다익스트라 알고리즘
    int Dijkstra() {

        class City implements Comparable<City> {
            final int city, cost;

            City(int city, int cost) {
                this.city = city;
                this.cost = cost;
            }

            public int compareTo(City c) {
                return this.cost - c.cost;
            }
        }

        int[] cost = new int[n];
        Arrays.fill(cost, INF);
        PriorityQueue<City> pq = new PriorityQueue<>();
        pq.add(new City(start, 0));
        cost[start] = 0;
        while (!pq.isEmpty()) {
            City curr = pq.poll();
            int currCity = curr.city;
            int currCost = curr.cost;
            if (cost[currCity] < currCost) // 이미 처리한 곳을 재방문한 경우
                continue;
            for (int i = 0; i < n; i++) {
                if (bus[currCity][i] == null) // currCity에서 i로 가는 버스가 없는 경우
                    continue;
                if (cost[i] > currCost + bus[currCity][i]) {
                    cost[i] = currCost + bus[currCity][i];
                    pq.add(new City(i, cost[i]));
                }
            }
        }
        return cost[end];
    }

    void solution() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        bw.write(Dijkstra() + "");
        bw.close();
    }

    public static void main(String[] args) throws IOException {
        new BOJ1916().solution();
    }
}