[Programmers] 배달

.

// 1 <= N <= 50
// 1 <= road <= 2000
// road : a b c -> a, b 마을 번호 c 걸리는 시간
// 도로는 여러개 가능
// 1 <= K <= 500,000
// 1번 마을에서 K이하 마을 갯수

// 주의할 점 : 0번 index는 사용안된다

// bfs로 하나씩 나아간다
// 최단 거리를 갱신하면서 나아간다 -> 이때 지금까지 왔던 경로를 기록한다.
// 여러 경로를 거쳐서 중복된 곳을 갈 때 최단거리가 갱신된다면 다시 가기

import java.util.PriorityQueue;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    class Node implements Comparable<Node>{
        int now;
        int length = 0;
        Node(int now, int N, int length){
            this.now = now;
            this.length = length;
        }
        
        public int compareTo(Node a){
            return a.length - this.length;
        }
    }
    public int solution(int N, int[][] road, int K) {
        int answer = 1;
        int roadLength = road.length;
        int[][] map = new int[N+1][N+1];
        int[] shortLength = new int[N+1];
        
        Arrays.fill(shortLength, Integer.MAX_VALUE);
        ArrayList<ArrayList<Integer>> mapLine = new ArrayList<>();
        
        for(int i = 0; i < N+1; i++){
            mapLine.add(new ArrayList<>());
        }
        for(int i = 0; i < roadLength; i++){
            int a = road[i][0], b = road[i][1];
            int length = road[i][2];

            if(a == 1){
                if(shortLength[b] == Integer.MAX_VALUE || shortLength[b] > length)
                    shortLength[b] = length;
            }else if(b == 1){
                if(shortLength[a] == Integer.MAX_VALUE || shortLength[a] > length)
                    shortLength[a] = length;
            }
            // 마을간 거리
            if(map[a][b] == 0 || map[a][b] > length){
                if(map[a][b] == 0){
                    mapLine.get(a).add(b);
                    mapLine.get(b).add(a);     
                }
                map[a][b] = length;
                map[b][a] = length;
            }
        }
        
        PriorityQueue<Node> q = new PriorityQueue<>();
        for(int i = 2; i < N+1; i++){
            if(shortLength[i] != Integer.MAX_VALUE){
                q.add(new Node(i, N, shortLength[i]));
            }
        }

        while(!q.isEmpty()){
            Node n = q.poll();
            for(int town : mapLine.get(n.now)){
                int totalLength = n.length+map[n.now][town];
                if(totalLength < shortLength[town] && totalLength <= K){
                    shortLength[town] = totalLength;
                    q.add(new Node(town, N, totalLength));                        
                }
            }
        }
        for(int i = 2; i < N+1; i++){
            if(shortLength[i] <= K){
                answer++;
            }
        }
        return answer;
    }
}

신경써줘야 하는 조건들이 있어 문제가 좀 꼬였었다. 다익스트라알고리즘을 알고있다면 쉽게 풀수 있는문제

배운 점 : Queue가아닌 PriorityQueue를 사용하면 더 빠르다.