[백준] 1916 최소비용 구하기 - Graph Theory / Java

• 문제 링크

1916번: 최소비용 구하기

 

• 풀이 과정

한 노드에서 다른 모든 노드까지의 최단 거리를 구하고,

음의 가중치가 없는 그래프이므로 Dijkstra 알고리즘을 활용한다.

 

모든 노드까지의 최단 거리를 저장할 dist 배열을 최대값으로 초기화하고,

각각의 간선의 시작점이 인접 리스트의 인덱스로써, 도착점과 가중치를 저장한다.

 

입력받은 시작점 source를 dijskstra 함수의 매개 변수로 전달하여 실행하고,

우선 순위 큐를 람다식을 통해 가중치 weight 를 오름차순 우선 순위로 지정한다.

 

우선 순위 큐에서 poll 한 값(Edge now = pq.poll())은 이동한 경로의 가중치의 합(now.weight)을 포함하고,

해당 값이 이동한 위치에 현재까지 갱신된 최단 경로보다 크다면(now.weight > dist[now.node]) 건너뛴다.

 

이동한 노드가 출발점으로써 이 노드에서 이동 가능한 도착점들을 모두 확인하여 

도착점의 누적된 최단 거리(dist[dest.node])가

출발점 최단 거리와 현재 경로의 가중치의 합(dist[src] + dest.weight)보다 클 경우,

도착점의 최단 거리를 작은 최단 거리값으로 갱신한다.

 

이렇게 각각의 노드까지의 최단 거리가 dist 배열에 저장되고,

이 중 목표 지점 destination 까지의 최단 거리를 꺼내어 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int[] dist;
    static List<Edge>[] list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        dist = new int[n + 1];
        list = new ArrayList[n + 1];

        Arrays.fill(dist, Integer.MAX_VALUE);

        for (int i = 1; i <= n; i++)
            list[i] = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            list[src].add(new Edge(dest, weight));
        }

        st = new StringTokenizer(br.readLine());
        int source = Integer.parseInt(st.nextToken());
        int destination = Integer.parseInt(st.nextToken());

        dijkstra(source);

        bw.write(dist[destination] + "\n");
        bw.flush();
    }

    private static void dijkstra(int source) {
        PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);

        pq.offer(new Edge(source, 0));
        dist[source] = 0;

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

            if (now.weight > dist[now.node])
                continue;

            int src = now.node;
            for (Edge dest : list[src]) {
                if (dist[dest.node] > dist[src] + dest.weight) {
                    dist[dest.node] = dist[src] + dest.weight;

                    pq.offer(new Edge(dest.node, dist[dest.node]));
                }
            }
        }
    }

    private static class Edge {
        int node, weight;

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

}