[programmers][X] 배달

17 Jul 2023 in Algorithm on Algorithm

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

import java.util.*;

class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        int[] scores = new int[N+1];
        Arrays.fill(scores,Integer.MAX_VALUE);
        scores[1] = 0;
        Map<Integer,List<Node>> m = new HashMap<>();

        for(int i = 1 ; i <= N ; i++) m.put(i,new ArrayList<>());

        for(int[] r : road){
            int temp1 = r[0];
            int temp2 = r[1];
            int score = r[2];

            m.get(temp1).add(new Node(temp2,score));
            m.get(temp2).add(new Node(temp1,score));
        }

        Queue<Node> q = new ArrayDeque<>();
        q.offer(new Node(1,0));

        while(!q.isEmpty()){
            Node temp = q.poll();

            List<Node> l = m.get(temp.out);
            for(Node n : l){
                int sum = scores[temp.out] + n.score;

                if(scores[n.out] > sum){
                    scores[n.out] = sum;
                    q.offer(n);
                }
            }
        }

        for(int s : scores){
            if(s <= K) answer++;
        }

        return answer;
    }
}

class Node{
    int out;
    int score;
    Node(int out, int score){
        this.out = out;
        this.score = score;
    }
}