이소영

package lv2; import java.util.Arrays; public class Solution { // 배달 private int solution(int N, int[][]road, int K) { // 1️⃣ final int INF = 987654321; int answer = 0; int[] dist = new int[N+1]; int[][] adj = new int[N+1][N+1]; boolean[] v = new boolean[N+1]; // 2️⃣ for (int i = 1; i < adj.length; i++) { Arrays.fill(adj[i], INF); adj[i][i] = 0; } for (int i = 0; i < road.length; i++) { if(adj[road[i][0]][road[i][1]] == INF) { adj[road[i][0]][road[i][1]] = road[i][2]; adj[road[i][1]][road[i][0]] = road[i][2]; } else { adj[road[i][0]][road[i][1]] = Math.min(adj[road[i][0]][road[i][1]], road[i][2]); adj[road[i][1]][road[i][0]] = Math.min(adj[road[i][1]][road[i][0]], road[i][2]); } } // 3️⃣ Arrays.fill(dist, INF); dist[1] = 0; // 4️⃣ int cnt = 0; while(cnt < N-1) { int min = INF; // 최소값을 비교하기 위해 무제한을 담은 최소값 변수 선언 int node = 0; // 가장 탐색하지 않은 마을 중 가장 최소한의 거리에 있는 마을 번호를 담을 변수 // 5️⃣ for (int i = 1; i < dist.length; i++) { if(!v[i] && dist[i] < min) { min = dist[i]; node = i; } } cnt++; v[node] = true; // 6️⃣ for (int i = 1; i < adj.length; i++) { if(!v[i] && adj[node][i] != INF && dist[i] > dist[node] + adj[node][i]) { dist[i] = dist[node] + adj[node][i]; } } } // 8️⃣ for (int i = 1; i < dist.length; i++) { if(dist[i] <= K) { answer++; } } return answer; } public static void main(String[] args) { Solution delivery = new Solution(); /*int N = 5; int[][] road = {{1, 2, 1}, {2, 3, 3}, {5, 2, 2}, {1, 4, 2}, {5, 3, 1}, {5, 4, 2}}; int K = 3*/; int N = 6; int[][] road = {{1, 2, 1}, {1, 3, 2}, {2, 3, 2}, {3, 4, 3}, {3, 5, 2}, {3, 5, 3}, {5, 6, 1}}; int K = 4; System.out.println(delivery.solution(N, road, K)); } }