[알고리즘] 배달 level2

문제

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

1번 마을부터 시작해서 각 마을의 최단경로를 구해 K(갈 수 있는 배달길이) 보다 작은 마을의 개수를 구하는 문제이다.
전형적인 다익스트라 문제이며 플로이드 워셜의 경우 모든 마을의 경우의 수를 구하기 때문에
다익스트라로 푸는게 더 효율적이다.
1. 각 road를 2차원 배열값으로 저장
2. distance를 저장하는 d배열값을 무한값으로 초기화 -> 최단경로를 구하기 위해
3. 다익스트라
-> 첫번째 마을(1번)을 우선순위큐 집어넣고 거리는 0(1번 -> 1번)
각 road를 꺼내 1번이랑 이어진 길을 찾음(2번 4번)
거리를 d[2]=Math.min(INF==d[2],0+1)(1번 -> 2번) d[4]=2(1번 -> 2번)
2번이랑 이어지느 road와 4번이랑 이어진 road값을 우선순위큐에 집어넣음
연결된 도로가 없어질때까지 반복
4. K값과 d배열값을 비교해 배달이 가능한 마을의 개수를 구함

코드

import java.util.*;
class Solution {
    static int[][] map;
    static int INF=(int)1e9;
    static int[] d=new int[51];
    static class Node implements Comparable<Node>{
        int index;
        int distance;
        Node(int index,int distance){
            this.index=index;
            this.distance=distance;
        }
        
        @Override
        public int compareTo(Node other){
            if(this.distance<other.distance){
                return -1;
            }
            return 1;
        }
    }
    public static void dijkstra(int start){
        d[start]=0;
        PriorityQueue<Node> pq=new PriorityQueue<>();
        pq.offer(new Node(start,0));
        while(!pq.isEmpty()){
            Node node=pq.poll();
            int now=node.index;
            int dst=node.distance;
            for(int i=1;i<map.length;i++){
                if(map[now][i]>=INF) continue;
                int cost=d[now]+map[now][i];
                if(cost<d[i]){
                    d[i]=cost;
                    pq.offer(new Node(i,cost));
                }
            }
        }
    }
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        Arrays.fill(d,INF);
        map=new int[N+1][N+1];
        for(int i=0;i<N+1;i++){
            Arrays.fill(map[i],INF);
        }

        for(int i=0;i<road.length;i++){
            if(map[road[i][0]][road[i][1]]>road[i][2]){
                map[road[i][0]][road[i][1]]=road[i][2];
                map[road[i][1]][road[i][0]]=road[i][2];
            }
        }
        
        dijkstra(1);
        
        for(int i=1;i<N+1;i++){
            if(d[i]<=K) answer++;
        }
        

        return answer;
    }
}