Programmers 12978 - 배달

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

프로그래머스

 

N개의 마을 중 K 시간 이하로 배달이 가능한 마을에서만 주문을 받는다.

시작점은 1번 마을이다.

가중치가 존재하는 최단거리 계산이다. 즉 다익스트라 알고리즘을 사용하면 될 것 같다.

1번으로부터 각 노드까지의 최단 거리를 계산하고 해당 최단 거리가 K 이하인 곳들의 개수를 세면 된다.

import java.util.*;
import java.util.stream.*;

class Solution {
    
    static class Node {
        int id;
        int distance;
        
        public Node(int id, int distance) {
            this.id = id;
            this.distance = distance;
        }
    }
    
    static final int INF = Integer.MAX_VALUE;
    static int[] distances;
    static Map<Integer, List<Node>> graph = new HashMap<>();
    
    public int solution(int N, int[][] road, int K) {
        distances = new int[N + 1];
        Arrays.fill(distances, INF);
        for (int i = 0; i <= N; i++) {
            graph.put(i, new ArrayList<>());
        }
        
        for (int[] edge : road) {
            graph.get(edge[0]).add(new Node(edge[1], edge[2]));
            graph.get(edge[1]).add(new Node(edge[0], edge[2]));
        }
    
        djikstra(1);

        return (int)IntStream.range(1, N + 1)
                        .filter(i -> distances[i] <= K)
                        .count();
    }
    
    private void djikstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));
        
        pq.add(new Node(start, 0));
        distances[start] = 0;
        
        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            int u = curr.id;
            
            if (distances[u] < curr.distance) continue;
           
            for (Node next : graph.get(u)) {
                int v = next.id;
                int weight = next.distance;
                
                if (distances[v] > distances[u] + weight) {
                    distances[v] = distances[u] + weight;
                    pq.add(new Node(v, distances[v]));
                }
            }
        }
    }
}