[프로그래머스/Java] 배달 Lv.2

문제

배달

---

풀이

다익스트라 알고리즘을 활용하여 1번 마을에서 다른 마을까지의 거리를 모두 구한 뒤 K와 대소비교한다.

---

풀이

import java.util.*;

class Solution {
    public int solution(int N, int[][] road, int K) {
        int[] dist = new int[N + 1];
        for (int i = 2; i < N + 1; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        int[][] graph = new int[N + 1][N + 1];
        for (int[] r : road) {
            graph[r[0]][r[1]] = graph[r[0]][r[1]] == 0 ? r[2] : Math.min(graph[r[0]][r[1]], r[2]);
            graph[r[1]][r[0]] = graph[r[0]][r[1]] == 0 ? r[2] : Math.min(graph[r[0]][r[1]], r[2]);
        }

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        pq.add(new Pair(1, 0));

        while (!pq.isEmpty()) {
            Pair cur = pq.poll();

            if (dist[cur.node] != cur.w) continue;

            for (int i = 1; i <= N; i++) {
                int nextW = graph[cur.node][i];

                if (nextW == 0) continue;
                if (dist[i] <= dist[cur.node] + nextW) continue;

                dist[i] = dist[cur.node] + nextW;
                pq.add(new Pair(i, dist[i]));
            }
        }

        int answer = 0;
        for (int i = 1; i <= N; i++) {
            if (dist[i] <= K) answer++;
        }

        return answer;
    }

    static class Pair implements Comparable {

        int node;
        int w;

        Pair(int node, int w) {
            this.node = node;
            this.w = w;
        }

        public int compareTo(Object o) {
            Pair other = (Pair) o;

            return this.w - other.w;
        }

        public String toString() {
            return "{" + node + ", " + w + "}";
        }
    }
}