프로그래머스 Lv.2: 배달

import java.util.*;

class Solution {
    public int solution(int N, int[][] road, int K) {
        // 1. 그래프 생성 (인접 리스트)
        List<int[]>[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] r : road) {
            int a = r[0], b = r[1], c = r[2];
            graph[a].add(new int[] {b, c});
            graph[b].add(new int[] {a, c});
        }

        // 2. 다익스트라 알고리즘
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0; // 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], time = current[1];

            if (time > dist[now]) continue;

            for (int[] edge : graph[now]) {
                int next = edge[0], nextTime = edge[1];
                if (dist[next] > dist[now] + nextTime) {
                    dist[next] = dist[now] + nextTime;
                    pq.add(new int[] {next, dist[next]});
                }
            }
        }

        // 3. K 이하인 마을 개수 계산
        int answer = 0;
        for (int i = 1; i <= N; i++) {
            if (dist[i] <= K) {
                answer++;
            }
        }

        return answer;
    }
}