문제 설명

1번 마을에서 K 시간 내에 배달 가능한 마을의 갯수 찾기

문제 접근

전형적인 다익스트라 문제. 시간을 줄이기 위해 선형탐색 대신 우선순위큐를 적용했고, 인접행렬 대신 인접리스트를 적용해서 시간 최적화를 시켰다.

풀이

import java.util.*;

class Solution {
    int[] table;
    final int INF = 10_0000_0000;
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        table = new int[N+1];
        ArrayList<Node>[] nodes = new ArrayList[N+1];
        for(int i = 1; i<=N; i++) {
            nodes[i] = new ArrayList();
        }
        
        for(int[] r: road) {
            nodes[r[0]].add(new Node(r[1], r[2]));
            nodes[r[1]].add(new Node(r[0], r[2]));            
        }
        
        PriorityQueue<Node> pq = new PriorityQueue<Node>((n1, n2)->{
            return n1.d - n2.d;
        });
        pq.add(new Node(1,0));
        Arrays.fill(table, INF);
        table[1] = 0;
        
        while (!pq.isEmpty()) {
            Node n = pq.poll();
            for(Node next:nodes[n.num]){
                if(table[next.num] > n.d + next.d) {
                    table[next.num] = n.d + next.d;
                    pq.add(new Node(next.num, table[next.num]));
                }
            }
        }
        
        for(int i =1; i<=N; i++){
            if(table[i] <= K) {
                answer++;
            }
        }
        return answer;
    }
}

class Node {
    final int num;
    final int d;
    Node(int num, int d) {
        this.num = num;
        this.d = d;
    }
}

PriorityQueue같은 제네릭 구조에다가 Comparator 를 적용할때는 제네릭을 지정해야 한다. 안그러면 타입 인식이 안되어서 강제형변환을 시켜야 함.