[백준 / 골드5] 1916 최소비용 구하기 (Java)

문제 보기

사용한 것

• 출발 도시에서 도착 도시까지의 버스 비용의 최소를 구하기 위한 다익스트라

풀이 방법

• 우선순위 큐로 구현한 다익스트라 알고리즘을 사용한다.
• 시작 정점의 비용을 0으로 초기화하고 pq에 넣어주면서 시작한다.
• pq에서 꺼낸 정점의 비용과 해당 정점이 가지고 있는 간선의 비용을 더한 값이 간선의 도착 정점의 비용보다 싸다면 교체한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        List<List<Node>> graph = new ArrayList<>();
        String[] line;
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            line = br.readLine().split(" ");
            int s = Integer.parseInt(line[0]);
            int e = Integer.parseInt(line[1]);
            int w = Integer.parseInt(line[2]);
            graph.get(s).add(new Node(e, w));
        }
        line = br.readLine().split(" ");
        int startCity = Integer.parseInt(line[0]);
        int endCity = Integer.parseInt(line[1]);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] dist = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        dist[startCity] = 0;
        pq.offer(new Node(startCity, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            if (node.w > dist[node.v]) {
                continue;
            }

            for (Node nextNode : graph.get(node.v)) {
                int nextDist = dist[node.v] + nextNode.w;
                if (nextDist < dist[nextNode.v]) {
                    dist[nextNode.v] = nextDist;
                    pq.offer(new Node(nextNode.v, nextDist));
                }
            }
        }

        System.out.println(dist[endCity]);
    }
}

class Node implements Comparable<Node> {

    int v;
    int w;

    public Node(int s, int w) {
        this.v = s;
        this.w = w;
    }

    @Override
    public int compareTo(Node o) {
        return w - o.w;
    }
}