[BOJ] 1916번 최소비용 구하기 (Java)

백준 1916번 최소비용 구하기

다익스트라 알고리즘

간단한 다익스트라 알고리즘을 구현하는 문제였지만, 메모리와 시간 제한이 타이트했다. 우선 순위 큐를 활용해서 빠른 시간 내에 문제를 해결해야 했다.

힘들었던 점

문제 설계는 쉬웠지만 아직 자바라는 언어를 다루는데 익숙하지 않아 힘들었다. ArrayList배열을 만들고 초기화는 과정에서 실수했다. 변수에 배열을 선언하는 순간 메모리를 공유하기 때문에 변수에 배열을 선언하지 않고 바로 초기화를 했어야 했다. 또한 배열을 채우는 메소드를 기억하지 못해 직접 반복문을 만들었었다.

import java.util.*;
import java.io.*;

public class Main {

    static ArrayList<Edge>[] table;
    static int [] dp;

    static class Edge {
        int e, c;

        Edge(int e, int c) {
            this.e = e;
            this.c = c;
        }
    }

    static int n;
    public static void main(String[] args) {
        try {
            int m, tmpX, tmpY, tmpCost;
            int [] tmp;
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st;
            n = Integer.parseInt(br.readLine());
            m = Integer.parseInt(br.readLine());
            PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.c - b.c);
            table = new ArrayList [n + 1];
            dp = new int [n + 1];
           
           // 배열 채우는 법
           Arrays.fill(dp, Integer.MAX_VALUE);
            
            // ArrayList 배열 초기화
            for(int i = 1; i <= n; i ++){
                table[i] = new ArrayList<Edge>();
            }
            while(m-- > 0) {
                st = new StringTokenizer(br.readLine());
                tmpX = Integer.parseInt(st.nextToken());
                tmpY = Integer.parseInt(st.nextToken());
                tmpCost = Integer.parseInt(st.nextToken());
                table[tmpX].add(new Edge(tmpY, tmpCost));
            }
            st = new StringTokenizer(br.readLine());
            tmpX = Integer.parseInt(st.nextToken());
            tmpY = Integer.parseInt(st.nextToken());
            pq.add(new Edge(tmpX, 0));
            
           // 우선순위큐를 활용
            while (!pq.isEmpty()) {
                Edge e = pq.poll();
                if (e.e == tmpY) {
                    System.out.println(e.c);
                    break;
                }
                if(dp[e.e] > e.c){
                    dp[e.e] = e.c;
                    for (Edge tmpE : table[e.e]) {
                        pq.add(new Edge(tmpE.e, tmpE.c + e.c));
                    }
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}