[프로그래머스] 배달 (Java)

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

코딩테스트 연습 - 배달

import java.util.*;

class Solution {
    static class Node implements Comparable<Node>{
        int id;
        int cost;
        Node(int id, int cost){
            this.id=id;
            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;
        ArrayList<ArrayList<Node>> adjList=new ArrayList<ArrayList<Node>>(N+1);
        for (int i=0; i<=N; i++){
            adjList.add(new ArrayList<Node>());
        }
        int[] dist=new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1]=0;
        for (int i=0; i<road.length; i++){
            int a=road[i][0];
            int b=road[i][1];
            int c=road[i][2];
            adjList.get(a).add(new Node(b,c));
            adjList.get(b).add(new Node(a,c));
        }
        PriorityQueue<Node> pq=new PriorityQueue<>();
        pq.add(new Node(1,0));
        while (!pq.isEmpty()){
            Node now=pq.poll();
            if (dist[now.id]<now.cost) continue;
            for (int i=0; i<adjList.get(now.id).size(); i++){
                Node next=adjList.get(now.id).get(i);
                if (dist[next.id]>now.cost+next.cost){
                    dist[next.id]=now.cost+next.cost;
                    pq.offer(new Node(next.id, dist[next.id]));
                }
            }
        }
        for (int i=1; i<=N; i++){
            if (dist[i]<=K){
                answer++;
            }
        }
        

        return answer;
    }
}

다익스트라를 활용해서 푸는 문제.

 

인접 리스트를 사용하니 좀 코드가 더럽다. 다른 분들의 코드를 보니 인접 리스트를 사용하지 않고 road[][] 를 이용해서, road배열을 쭉 돌면서 road[i][0], road[i][1]이 현재 뽑은 번호일 경우, 그 이웃의 dist를 체크하면서 현재 거리+이웃까지 가는 거리가 dist배열의 값보다 작으면 갱신해주고, pq에 이웃 번호와 이웃의 거리를 넣어준다.