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

#문제

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

코딩테스트 연습 - 배달

#풀이

다익스트라 알고리즘을 사용하면 풀 수 있다.

 

#소스코드

import java.util.*;

// 노드의 연결된 노드와 거리를 가짐
class Edge {
    int to; 
    int distance;
    
    public Edge(int to, int distance){
        this.to = to;
        this.distance = distance;
    }
}

// 시작 노드에서 특정 노드에 도착하기 까지 가능한 거리
class Info {
    int node; 
    int distance;
    
    public Info(int node, int distance){
        this.node = node;
        this.distance = distance;
    }
}


class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        
        // 해당 노드까지의 최단 거리를 담을 배열 생성
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);        
        
        // 각 노드의 인접 노드 리스트를 넣어줄 배열 생성
        ArrayList<Edge>[] edges = new ArrayList[N+1];
        for(int i = 0; i <= N; i++){
            edges[i] = new ArrayList<Edge>();            
        }
        
        // 거리 정보를 넣어줄 힙 생성
        PriorityQueue<Info> pq = new PriorityQueue<Info>(new Comparator<Info>(){
            @Override
            public int compare(Info i1, Info i2){
                return i1.distance - i2.distance;
            }
        });
        
        // 데이터를 담는다.
        for(int i = 0; i < road.length; i++){
            for(int j = 0; j < 3; j++){
                edges[road[i][0]].add(new Edge(road[i][1], road[i][2]));
                edges[road[i][1]].add(new Edge(road[i][0], road[i][2]));
            }
        }
        
        // 1번 Node부터 시작
        dist[1] = 0;
        pq.offer(new Info(1, dist[1]));
        
        while(!pq.isEmpty()) { 
            Info info = pq.poll();  
            if(info.distance > dist[info.node]) continue;
            for(Edge adj : edges[info.node]){
                 if(info.distance + adj.distance < dist[adj.to]){
                     dist[adj.to] = info.distance + adj.distance;
                     pq.offer(new Info(adj.to, dist[adj.to]));
                 }
            }
        }
        
        for(int i = 1; i < dist.length; i++){
            if(dist[i] <= K) answer++;
        }
     
        return answer;
    }
}