문제 - 배달

문제접근

단일 시작점에서 다른 모든 정점으로의 최단 거리를 찾기 위해서 다익스트라 알고리즘을 사용했다.
최소비용을 위해 우선순위큐를 이용해서 시간복잡도를 조금더 줄여보았다.

소스코드

import java.util.*;

class Solution {
    static ArrayList<ArrayList<Node>> graph;
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        //그래프 초기화
        graph = new ArrayList<ArrayList<Node>>();
        
        for(int i=0;i < N+1;i++)
        {
            graph.add(new ArrayList<Node>());
        }
        //간선 추가
        for(int roads[] : road)
        {
            graph.get(roads[0]).add(new Node(roads[1],roads[2]));
            graph.get(roads[1]).add(new Node(roads[0],roads[2]));
        }
        
        //다익스트라 최소비용 계산 
        int []dist = new int[N+1];
        for(int i=0;i<N+1;i++)
        {
            dist[i] = Integer.MAX_VALUE;
        }
        //최소비용을 위한 우선순위큐
        PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2) -> Integer.compare(o1.cost,o2.cost));
        
        //1번마을에서 시작
        pq.offer(new Node(1,0));
        dist[1] = 0;
        
        while(!pq.isEmpty())
        {
            Node cnt = pq.poll();
            //해당 노드의 비용이 현재 dist배열에 기록된 내용보다 크다면 고려할 필요가 없으므로 스킵
            if(dist[cnt.num] < cnt.cost) continue;
            
            //인접한 노드 탐색
            for(int i=0;i<graph.get(cnt.num).size();i++)
            {
                Node next = graph.get(cnt.num).get(i);
                
                if(dist[next.num] > cnt.cost + next.cost)
                {
                    dist[next.num] = cnt.cost + next.cost;
                    pq.offer(new Node(next.num,dist[next.num]));
                }
            }
            
        }
    
        
        for(int i=1;i<N+1;i++)
        {
            if(dist[i] <= K )
            {
                answer++;
            }
        }
        return answer;
    }
    
    class Node{
        int num;
        int cost;
        
        public Node(int num,int cost)
        {
            this.num = num;
            this.cost = cost;
        }
    }
}

참고 사이트