프로그래머스 - 배달 - 다익스트라 - Java

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12978

2. 풀이

다익스트라로 시작점 ~ 다른 정점까지의 최단경로를 구하고, 그것이 K시간 이하로 배달이 가능한지 보았다.

✨핵심 Point

d[시작점] = 0으로 시작해야 한다.

PriorityQueue에 넣을려면 class에 반드시 implemenst Comparable을 수행해야한다.
(파이썬과 다르게 자바는 두 개이상의 인자를 PriorityQueue에 담을때는 무조건 우선순위를 명시해줘야한다..)

3. 전체 코드

import java.util.*;

class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        int d[] = new int[N+1];
        ArrayList<ArrayList<Node>> list = new ArrayList<>();
        
        for(int i = 0; i <= N; i++){
            d[i] = (int)1e9;
            list.add(new ArrayList<>());
        }
        
        for(int i = 0; i < road.length; i++){
            int a = road[i][0];
            int b = road[i][1];
            int c = road[i][2];
            
            list.get(a).add(new Node(c, b));
            list.get(b).add(new Node(c, a));
        }
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, 1));
        d[1] = 0;
        
        while(!pq.isEmpty()){
            Node node = pq.poll();
            
            if(d[node.num] < node.cost) continue;
            
            for(Node nowNode : list.get(node.num)){
                int costs = node.cost + nowNode.cost;
                
                if(costs < d[nowNode.num]){
                    d[nowNode.num] = costs;
                    pq.add(new Node(costs, nowNode.num));
                }
            }
        }
        
        for(int dInt : d){
            if(dInt <= K) answer++;
        }
        
        return answer;
    }
    
    public class Node implements Comparable<Node> {
        int cost;
        int num;
        
        public Node(int cost, int num){
            this.cost = cost;
            this.num = num;
        }
        
        @Override
        public int compareTo(Node other){
            return Integer.compare(this.cost, other.cost);
        }
    }
}