[JAVA] 백준 9893 - Paths

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

정점과 간선 리스트가 주어졌을 때, 0 -> 1까지 가는 최소 거리, 최소 비용 가중치를 구하는 문제이다.

짧으면 무조건 1 순위, 경로의 길이가 같으면 비용을 비교한다.

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

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 roadCount = info[1];
        List<N18352> nodeList = new ArrayList<>();
        for (int i = 0; i < nodeCount; i++) {
            nodeList.add(new N18352(i));
        }
        nodeList.get(0).weight = 0;
        nodeList.get(0).count = 0;
        PriorityQueue<N18352> pq = new PriorityQueue<>();
        for (int i = 0; i < roadCount; i++) {
            int[] road = getArray(br.readLine());
            nodeList.get(road[0]).roadList.add(new V18352(road[1],road[2]));
        }
        pq.offer(nodeList.get(0));
        while(!pq.isEmpty()){
            N18352 node = pq.poll();
            List<V18352> roadList = node.roadList;
            int c = node.count;
            for (V18352 v18352 : roadList) {
                int targetNode = v18352.to;
                if (nodeList.get(targetNode).count > c + 1) { //count가 더 적어질 때
                    nodeList.get(targetNode).count = c + 1;
                    nodeList.get(targetNode).weight = node.weight + v18352.weight;
                    pq.offer(nodeList.get(targetNode));
                } else if (nodeList.get(targetNode).count == c + 1) { //count가 같으면 가중치로
                    if (node.weight + v18352.weight < nodeList.get(targetNode).weight) {
                        nodeList.get(targetNode).weight = node.weight + v18352.weight;
                        nodeList.get(targetNode).count = c + 1;
                        pq.offer(nodeList.get(targetNode));
                    }
                }
            }
        }
        System.out.println(nodeList.get(1).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 N18352 implements Comparable<N18352>{
    int value;
    int weight = Integer.MAX_VALUE;
    int count = Integer.MAX_VALUE;
    List<V18352> roadList = new ArrayList<>();
    N18352(int value){
        this.value = value;
    }
    @Override
    public int compareTo(N18352 other){
        int s = this.count-other.count;
        if(s==0) return this.weight - other.weight;
        return s;
    }
}

class V18352{
    int to;
    int weight;
    V18352(int t, int w){
        this.to = t;
        this.weight = w;
    }
}