백준 1916 최소비용 구하기 - JAVA

문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.util.*;
import java.io.*;
 
class Node implements Comparable<Node> {
    int end;
    int weight;
    
    Node(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Node n) {
        return Integer.compare(this.weight, n.weight);
    }
}
public class Main{
    static int N, M;
    static List<List<Node>> list = new ArrayList<>();
    static int[] dist;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        } 
        
        StringTokenizer st;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            list.get(a).add(new Node (b, cost));
        } 
        
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        bw.write(String.valueOf(dijkstra(start, end)));
        bw.flush();
    }
 
    private static int dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        dist[start] = 0;
        
        while(!pq.isEmpty()) {
            Node current = pq.poll();
            int currentNode = current.end;
            int currentCost = current.weight;
            if (currentNode == end) return currentCost; 
            if (dist[currentNode] >= currentCost) {
                for (Node node : list.get(currentNode)) {
                    int nextNode = node.end;
                    int nextCost = node.weight;
                    if (dist[nextNode] > currentCost + nextCost) {
                        dist[nextNode] = currentCost + nextCost;
                        pq.offer(new Node (nextNode, dist[nextNode]));
                    }
                } 
            }
        }
        return dist[end];
    }
}

 

알고리즘 설명

---

'다익스트라'는 초등교육 또는 중등교육에서 가장 빠른 길찾기 같은 제목으로 한번씩 접해보셨을 단어라고 생각합니다. 아시는 바와 같이 다익스트라 알고리즘은 최단 경로 알고리즘 중 하나로, 그래프에서 출발 지점의 노드에서 다른 노드까지의 최단거리 또는 최소비용을 탐색하는 알고리즘입니다. 우선순위 큐의 자료구조를 활용합니다. 단, 간선의 가중치가 양수일 경우에만 동작합니다.

 

알고리즘의 핵심은 우선순위 큐(Priority Queue)를 이용하여 '가장 짧은 거리'를 가진 노드를 우선적으로 탐색하고, 해당 거리를 거리 배열의 해당 노드 위치에 매핑합니다. 그 다음, 현재 노드에서 인접한 노드로 가는 거리를 계산하고, 해당 거리가 매핑된 거리보다 더 짧으면 새로운 거리로 갱신하는 작업을 반복하여 출발 노드로부터의 최단 거리를 찾는 것입니다.

 

해당 코드에서 배열이 아닌 객체를 사용한 이유는 우선순위 큐는 PriorityQueue에 들어간 원소들이 어떤 기준에 따라 먼저 뽑힐지에 대한 기준을 정해야하기 때문입니다. 간선의 무게를 노드 별로 저장해야 하므로 객체를 사용하여 도착노드와 가중치를 저장하였습니다. 이후,  Comparble인터페이스를 implements하여 Node끼리 값을 비교할 수 있도록했습니다. 꼭 객체를 사용하지 않고, PriorityQueue선언 시에 PriorityQueue<long[]> pq =newPriorityQueue<>((a, b) -> Long.compare(a[1], b[1])); 이런식으로 기준을 정해줘도 되지만, 객체가 배열에 비해 직관적이고 가독성이 좋기때문에 도착정보와 간선의 가중치를 객체에 저장하였습니다.

 

객체

---

객체는 배열과 달리 사용자 정의 타입을 만들어 많은 데이터를 필드에 저장할 수 있습니다. 간단히 말해 같은 패키지 내부에서 public이나 default로 선언된 클래스 객체에서 선언하고 저장한 변수를  외부에서 캡슐화된 객체 함수를 통해 직접적으로 변수에 접근을 할 수 있기 때문입니다. 코드를 예로 들자면, Node 클래스는 접근 제어자를 지정하지 않았기 때문에 default 접근 제어자가 적용됩니다. Node에서 선언한 target변수와 value변수는 default 접근 제어자를 통해 접근이 가능하므로 코드의 58~60번째 줄처럼 직관적인 접근이 가능합니다.

 

하지만 만약 접근제어자가 private라면 아래와 같이 getter메서드를 통해 간접적으로 접해야 합니다.
<Node 선언>

class Node implements Comparable<Node> {
    private int target;  // 외부에서 직접 접근 불가
    private int value;   // 외부에서 직접 접근 불가
 
    Node(int target, int value) {
        this.target = target;
        this.value = value;
    }
 
    public int getTarget() {       // target 값을 읽기 위한 getter
        return target;
    }
 
    public int getValue() {        // value 값을 읽기 위한 getter
        return value;
    }
 
    @Override
    public int compareTo(Node n) {
        return value - n.value;
    }
}
 

<private로 Node 클래스를 선언한경우의 58~60번째 줄>

Node current = pq.poll();
            int currentNode = current.getTarget();
            int currentCost = current.getValue();

@Override의 경우에는 implements한 Comparable<T>인터페이스에서 노드의 순서를 정렬할 기준으로 compareTo메서드를 통하여 오름차순으로 정렬한 것입니다. 

 

- 참고 -

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Comparable.html

 

코드 해석

---

각 간선의 종착지와 거리를 리스트에 Node객체로 저장하고 시작노드의 거리를 0으로 설정하고 우선순위 큐(pq)에 삽입합니다.

큐에서 거리가 가장 짧은 Node를 추출하고, 해당 노드와 연결된 노드를 상대로 다익스트라 알고리즘을 실행하면서 더 짧은 경로 발견시 dist를 업데이트 후, pq에 삽입합니다. 도착 노드의 최단거리(dist[end])를 출력합니다.