[ 프로그래머스 ] #12978 : 배달 - JAVA

🔗 배달

import java.util.*;

class Solution {
    public int solution(int N, int[][] road, int K) {
        // 그래프를 인접 리스트 형태로 초기화
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] r : road) {
            int a = r[0], b = r[1], c = r[2];
            graph.get(a).add(new int[] { b, c });//도착 노드, 시간
            graph.get(b).add(new int[] { a, c });
        }

        // 다익스트라 알고리즘
        // 최단 거리 배열 및 우선순위 큐
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.add(new int[] { 1, 0 });// 시작점

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int now = current[0]; // 현재 노드
            int nowCost = current[1]; // 노드까지 시간 

            if (nowCost > dist[now]) continue;

            // 저장된 시간보다 최소라면 반복
            for (int[] neighbor : graph.get(now)) {
                int next = neighbor[0];
                int nextCost = nowCost + neighbor[1];

                if (nextCost < dist[next]) {// 작으면 갱신
                    dist[next] = nextCost;
                    pq.add(new int[] { next, nextCost });// 다음 반복을 위해 큐에 저장 
                }
            }
        }

        // K 이하로 도달할 수 있는 마을의 수 계산
        int count = 0;
        for (int d : dist) {
            if (d <= K) count++;
        }

        return count;
    }
}