[lv2] 배달

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

 

1번(코드에선 0번) 노드를 기준으로, 다익스트라를 통해 도달하는 비용이 k 이하인 노드의 개수를 출력한다.

 

노드 간 간선이 여러 개일 수 있는데, 이는 비용이 최소인 간선 하나만 사용한다.

또한, 1번 노드에서 1번 노드로 가는 경우도 cnt해야 함에 주의한다.

 

import java.util.*;

class Solution {
    public int solution(int N, int[][] road, int K) {
        int MAX = Integer.MAX_VALUE / 2;

        int[][] graph = new int[N][N];

        int[] cost = new int[N];
        Arrays.fill(cost, MAX);
        cost[0] = 0;

        for(int i=0; i<N; i++)
            Arrays.fill(graph[i], MAX);

        for(int i=0; i<road.length; i++) {
            int a = road[i][0] - 1;
            int b = road[i][1] - 1;
            int c = road[i][2];

            graph[a][b] = graph[b][a] = Math.min(graph[a][b], c);
        }

        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0});

        while(!q.isEmpty()) {
            int[] info = q.poll();
            int e = info[0];
            int val = info[1];

            for(int i=0; i<N; i++) {

                if(graph[e][i] + val < cost[i]) {
                    cost[i] = graph[e][i] + val;
                    q.offer(new int[]{i, cost[i]});
                }
            }
        }

        int ans = 0;

        for(int c : cost) {
            if(c <= K)
                ans++;
        }

        return ans;
    }
}