programmers_배달_java

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

프로그래머스

import java.util.*;
class Solution {   
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        // 간선 정보 리스트
        List<Edge>[] edges = new List[N+1];
        for (int i = 1; i<= N; i++){
            edges[i] = new ArrayList<>();
        }
        // 간선 정보 입력
        for (int[] edge : road){
            edges[edge[0]].add(new Edge(edge[1], edge[2]));
            edges[edge[1]].add(new Edge(edge[0], edge[2]));
        }

        int[] distance = calDistanc(N, 1, edges);
        answer = deliveryVilidge(distance, K, N);
        return answer;
    }

    // start로 부터 각 마을까지의 최단거리 계산
    public int[] calDistanc(int N, int start, List<Edge>[] edges){
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int[] distance = new int[N+1];
        Arrays.fill(distance, 987654321);
        pq.offer(new Edge(start, 0));
        distance[start] = 0;

        while (!pq.isEmpty()){
            Edge now = pq.poll();

            for (Edge e : edges[now.to]){
                if (distance[e.to] > distance[now.to] + e.cost){
                    distance[e.to] = distance[now.to] + e.cost;
                    pq.offer(e);
                }
            }
        }

        return distance;
    }
    
    // 배달 가능 마을 개수
    public int deliveryVilidge(int[] distance, int K, int N){
        int cnt = 0;

        for (int i = 1; i<= N; i++){
            if (distance[i] <= K){
                cnt++;
            }
        }

        return cnt;
    }

    //간선 정보 클래스
    public class Edge implements Comparable<Edge>{
        int to;
        int cost;
        public Edge(int to, int cost){
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost;
        }
    }
}