[Programmers / Level 2] 12978. 배달 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12978
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/배달

입출력 조건

입출력 예시

문제 이해

• 1번 마을에서 다른 마을까지 K 시간 이하로 배달할 수 있는 마을 수를 구하는 문제

알고리즘

풀이 시간 : 27분

• 그래프 인접 리스트 -> 양방향 도로
• 다익스트라 알고리즘 : 1번 마을부터 각 마을까지 최단 거리 계산
  • PriorityQueue 사용
  • 거리가 줄어들 때만 큐에 추가
• 거리 배열에서 K 이하인 마을의 수 카운트

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) {
            graph.get(r[0]).add(new int[]{r[1], r[2]});
            graph.get(r[1]).add(new int[]{r[0], r[2]});
        }

        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{1, 0});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int now = cur[0], cost = cur[1];

            if (cost > dist[now]) continue;

            for (int[] next : graph.get(now)) {
                int to = next[0], time = next[1];
                if (dist[to] > cost + time) {
                    dist[to] = cost + time;
                    pq.offer(new int[]{to, dist[to]});
                }
            }
        }

        int count = 0;
        for (int i = 1; i <= N; i++) {
            if (dist[i] <= K) count++;
        }

        return count;
    }
}

결과