[JAVA] 백준 5972 - 택배 배송

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

일반적인 다익스트라 문제이다.

두 정점을 잇는 간선의 개수가 1개 이상이라 최솟값만 저장하도록 노드 클래스에 HashMap으로 최솟값만 먼저 받고, 생성된 Key-Value 쌍을 간선list로 변환해 저장한 후 다익스트라를 돌렸다. 

중복간선 처리는 다익스트라 내부에서 충분히 가능하니 굳이 HashMap을 사용하지 않아도 되고, 

NodeClass도 weight 배열로 가능할 것 같다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        int nodeCount = info[0];
        int vertexCount = info[1];
        List<N5972> nodeList = new ArrayList<>();
        for (int i = 0; i <= nodeCount; i++) {
            nodeList.add(new N5972(i));
        }
        for (int i = 0; i <vertexCount; i++) {
            int[] roadInfo = getArray(br.readLine());
            int from = roadInfo[0];
            int to = roadInfo[1];
            int weight = roadInfo[2];
            nodeList.get(from).put(to,weight);
            nodeList.get(to).put(from,weight);
        }
        for (int i = 0; i <= nodeCount; i++) {
            nodeList.get(i).convert();
            nodeList.get(i).map.clear();
        }
        PriorityQueue<N5972> pq = new PriorityQueue<>();
        nodeList.get(1).weight = 0;
        boolean[] visited = new boolean[nodeCount+1];
        pq.offer(nodeList.get(1));
        visited[1] = true;
        while(!pq.isEmpty()){
            N5972 target = pq.poll();
            int value = target.value;
            int weight = target.weight;
            List<V5972> vertexList = target.vertexList;
            visited[value] = true;
            for (int i = 0; i < vertexList.size(); i++) {
               V5972 v = vertexList.get(i);
               if(visited[v.to]) continue;
               N5972 n = nodeList.get(v.to);
               if(weight + v.weight < n.weight){
                   n.weight = weight + v.weight;
                   pq.offer(n);
               }
            }
        }

        System.out.println(nodeList.get(nodeCount).weight);
    }
    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class N5972 implements Comparable<N5972>{
    int value;
    int weight = Integer.MAX_VALUE;
    HashMap<Integer,Integer> map = new HashMap<>();
    List<V5972> vertexList = new ArrayList<>();
    N5972(int value){
        this.value = value;
    }
    void put(int to, int weight){
        if(map.containsKey(to)){
            if(map.get(to)>weight){
                map.put(to,weight);
            }
        }else map.put(to,weight);
    }
    @Override
    public int compareTo(N5972 other){
        return this.weight - other.weight;
    }

    void convert(){
        this.vertexList = this.map.keySet().stream().map(x -> new V5972(this.value,x,map.get(x))).collect(Collectors.toList());
    }
}

class V5972{
    int from;
    int to;
    int weight;
    V5972(int f, int t, int w){
        this.from = f;
        this.to = t;
        this.weight = w;
    }
}