[프로그래머스] [Level2] 배달JAVA

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

코딩테스트 연습 - 배달

[문제]

[풀이]

특정 거리까지의 마을만 배달이 가능하기 때문에 모든 정점에 대해 거리의 합을 알아야 한다
하지만 출발지는 고정되어 있다. => 다익스트라 알고리즘 이용

각 정점에 대한 거리 배열을 Distance라고 하면 주어진 K 보다 낮은 값을 가진 마을의 개수를 카운트 하면 된다.

import java.util.stream.*;
import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;

import java.util.*;
import java.io.*;

class Solution {

    ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        for(int i=0;i<=N;i++) graph.add(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]));
        }

        answer = getTownCount(1,graph,K);
        return answer;
    }

    private int getTownCount(int start, ArrayList<ArrayList<Node>> graph, int k) {


        int[] distance = new int[graph.size()];
        Arrays.fill(distance,Integer.MAX_VALUE);
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);

        distance[start]=0;
        pq.add(new Node(start,0));
        while (!pq.isEmpty()){
            Node cur = pq.poll();

            if(distance[cur.node] < cur.weight)
                continue;

            for (Node next : graph.get(cur.node)) {

                if(distance[next.node] > distance[cur.node]+next.weight ){
                    distance[next.node] = distance[cur.node]+next.weight;
                    pq.add(new Node(next.node,distance[next.node]));
                }
            }
        }

        return (int) stream(distance).filter(dist->dist<=k).count();
    }

    static class Node{
        int node,weight;

        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }
}