[프로그래머스-JAVA, 자바] 배달

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

프로그래머스

 
- 다익스트라 알고리즘 활용

import java.util.*;

class Solution {
	
	static class Node implements Comparable<Node>{
		int idx, cost;
		Node(int idx, int cost){
			this.idx = idx;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Node o) {
			if(this.cost < o.cost) return -1;
			if(this.cost > o.cost) return 1;
			return 0;
		}
	}
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        
        ArrayList<Node>[] al = new ArrayList[N+1]; 
        for(int i=0 ; i<N+1 ; i++)
        	al[i] = new ArrayList<>();
        
        for(int i = 0; i<road.length ; i++) { // <= !!
        	al[road[i][0]].add(new Node(road[i][1], road[i][2]));
        	al[road[i][1]].add(new Node(road[i][0], road[i][2]));
        }
        
        int[] dist = new int[N+1];
        for(int i=0; i<N+1 ; i++) {
        	dist[i] = Integer.MAX_VALUE;
        }
        dist[1] = 0;
        
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(1, 0));
        
        while(!q.isEmpty()) {
        	Node now = q.remove();
        	int nowIdx = now.idx;
        	int nowCost = now.cost;
        	       	
        	for(int i=0 ; i<al[nowIdx].size() ; i++) {
        		Node next = al[nowIdx].get(i);
        		int nextIdx = next.idx;
        		int nextCost = next.cost;
        		
        		if(dist[nextIdx] >  dist[nowIdx] + nextCost) {
        			dist[nextIdx] = dist[nowIdx] + nextCost;
        			q.add(new Node(nextIdx, dist[nextIdx]));
        		}
        	}
        }
        
        for(int i=1 ; i<N+1 ; i++) {
        	if(dist[i]<= K)
        		answer++;
        }

        return answer;
    }
}