프로그래머스 배달

문제

풀이

다익스트라로 마을별 최단 거리를 구해주고 k이하의 마을을 카운트

---

코드

import java.util.*;
class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 1;
        d=new int[N+1];
        edges=new ArrayList[N+1];
        for(int i=1;i<N+1;i++)edges[i]=new ArrayList<>();
        int max=0;
        for(int i=0;i<road.length;i++){
            int a=road[i][0];
            int b=road[i][1];
            int c=road[i][2];
            edges[a].add(new Edge(b,c));
            edges[b].add(new Edge(a,c));
            max+=c;
        }
        for(int i=1;i<N+1;i++)d[i]=max+1;
        dijk();
        for(int i=2;i<N+1;i++){
            if(d[i]<=K)answer++;
        }
        return answer;
    }
    
    static int[] d;
    static ArrayList<Edge>[] edges;
    
    static 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;
        }
    }
    
    static void dijk(){
        d[1]=0;
        PriorityQueue<Edge> pq=new PriorityQueue<>();
        pq.add(new Edge(1,0));
        while(!pq.isEmpty()){
            Edge tmp=pq.poll();
            int now=tmp.to;
            int now_cost=tmp.cost;
            if(d[now]<now_cost)continue;
            for(Edge e:edges[now]){
                int next=e.to;
                int next_cost=now_cost+e.cost;
                if(d[next]>next_cost){
                    pq.add(new Edge(next,next_cost));
                    d[next]=next_cost;
                }
            }
        }
    }
}

#다익스트라