백준 1916 최소비용 구하기 Java [다익스트라]

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

1916번: 최소비용 구하기

 

다익스트라 알고리즘을 사용해서 풀면 된다

끝까지 돌 필요 없이 도착 도시에 최초로 방문할 때 break해준다

 

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


public class Main {
    static final int INF = 200_000_000;
    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());
        boolean[] vtd = new boolean[N+1];
        List<int[]>[] nodes = new ArrayList[N+1];
        for (int n = 0; n <= N; n++) {
            nodes[n] = new ArrayList<>();
        }
            int[] distance = new int[N+1];
        Arrays.fill(distance, INF);
        for (int m = 0; m < M; m++) {
            int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            nodes[arr[0]].add(new int[]{arr[1], arr[2]});
        }


        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int start = arr[0];
        int end = arr[1];
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        queue.add(new int[]{start, 0});
        distance[start] = 0;

        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            if (now[0] == end) {
                System.out.println(now[1]);
                break;
            }
            if (vtd[now[0]]) continue;
            vtd[now[0]] = true;
            for (int[] value : nodes[now[0]]) {
                if (distance[value[0]] > now[1] + value[1]) {
                    distance[value[0]] = now[1] + value[1];
                    queue.add(new int[]{value[0], distance[value[0]]});
                }
            }
        }
    }
}

피드백

nodes 리스트에 Arrays.fill(nodes, new int[]{}) 를 사용하니까 모두 같은 주소값으로 초기화되어 다시 하나씩 넣어줬다

우선순위큐 비교 연산을 자동완성에 의지하고 있는데 코테를 위해 공부해야할 필요성이 느껴진다

비슷한 문제 (1753번) 풀때 List 대신 HashMap을 사용하니까 시간초과가 떠서 이번엔 처음부터 List를 사용해서 풀었다

 

자료구조별 성능 비교를 해둔 블로그를 보고 List를 사용했다

https://12bme.tistory.com/91 

[자바성능] 자료형 성능 비교