[백준]1916. 최소비용 구하기

📄 링크

최소비용 구하기

---

💡 문제 분석

출발 지점과 도착지점이 제시되어 있고 간선에 가중치가 붙어 있기 때문에 다익스트라 혹은 벨만-포드로 풀 수 있다고 생각했습니다. 음의 가중치가 없어서 굳이 벨만-포드는 쓰지 않고 다익스트라를 사용했습니다

우선순위큐 정렬을 할 때 comparable을 쓸 때와 comparator 혹은 lambda 할수를 쓸 때 메모리와 시간이 많이 차이가 나는 것을 알게 되었습니다.
여유가 되는 문제들은 lambda를 사용하고 시간이 빠듯하면 comparable을 사용하는 것이 좋을 것 같습니다.

---

⌨️ 코드

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

public class _1916_최소비용구하기 {

    static class Edge implements Comparable<Edge> {
        int to, weight;

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

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }
    static int N, M;
    static List<Edge>[] adj;
    static boolean[] visited;
    static int S, E;

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        adj = new ArrayList[N + 1];
        for(int i = 0; i < N + 1; i++) {
            adj[i] = new ArrayList<>();
        }
        StringTokenizer st;
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            adj[from].add(new Edge(to, w));
        }
        st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        // 다익스트라 시작
        int[] ret = Dijkstra();
        System.out.println(ret[E]);
    }

    public static int[] Dijkstra() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[S] = 0;
        pq.offer(new Edge(S, 0));
        while(!pq.isEmpty()) {
            Edge cur = pq.poll();
            if(cur.weight > dist[cur.to]) continue;
            for(int i = 0; i < adj[cur.to].size(); i++) {
                int next = adj[cur.to].get(i).to;
                int nextDistance = adj[cur.to].get(i).weight + cur.weight;
                if(nextDistance < dist[next]) {
                    dist[next] = nextDistance;
                    pq.add(new Edge(next, nextDistance));
                }
            }
        }
        return dist;
    }
}

---

📋 회고

• 평범한 최소 비용 문제
• 다익스트라 구현