[프로그래머스] 배달

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

코딩테스트 연습 - 배달

2021-07-29

---

import java.util.*;
class Solution {
   static int[] dist;
   static List<List<Node>> list;
   static class Node implements Comparable<Node> {
        int val;
        int cost;
        public Node(int val, int cost) {
            this.val = val;
            this.cost = cost;
        }
 
       @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        list = new ArrayList<>();
        dist = new int[N+1];
        for(int i = 0; i <= N; i++) {
            list.add(new ArrayList<>()); // init
            dist[i] = 987654321;
        }
 
        for (int[] ints : road) {
            list.get(ints[0]).add(new Node(ints[1], ints[2]));
            list.get(ints[1]).add(new Node(ints[0], ints[2]));
        }
 
        boolean[] vtd = new boolean[N+1];
        PriorityQueue<Node> q = new PriorityQueue<>();
        vtd[0] = true;
        dist[1] = 0;
        q.add(new Node(1, 0));
 
        while(!q.isEmpty()) {
            int cur = q.poll().val;
 
            if(vtd[cur]) continue;
            vtd[cur] = true;
 
            for(Node n: list.get(cur)) {
                if(dist[n.val] > dist[cur] + n.cost) {
                    dist[n.val] = dist[cur] + n.cost;
                    q.add(new Node(n.val, dist[n.val]));
                }
            }
        }
        for(int i = 1; i < dist.length; i++) if(dist[i] <= K) answer++;
        return answer;
    }
}

#문제풀이

 

우선순위 큐를 이용한 다익스트라 알고리즘을 활용하여 풀었다.