> 문제
문제 : [배달]
> 문제풀이
문제에서 노드간 연결하는 간선이 두개 이상일 수 있기 때문에 가장 작은값을 저장하였고,
1번 마을(0번 노드)에서 시작하여 각 노드에 도달하는 거리가 최솟값이 되도록 다익스트라를 적용하였다.
시작점을 제외한 모든 노드를 최댓값으로 초기화하고, 작은 값으로 계속 갱신해준다.
소스는 다음과 같다.
import java.util.*;
class Solution {
static final int MAX_TIME_VALUE = 500000;
public int solution(int N, int[][] road, int K) {
int[][] map = new int[N][N];
for(int i=0; i<road.length; i++){
int a = road[i][0]-1;
int b = road[i][1]-1;
int c = road[i][2];
if(map[a][b] == 0 || map[a][b] > c){
map[a][b] = c;
map[b][a] = c;
}
}
int[] nodes = new int[N];
for(int i=1; i<nodes.length; i++){
nodes[i] = MAX_TIME_VALUE;
}
Queue<Integer> qu = new LinkedList<>();
qu.add(0);
while(!qu.isEmpty()){
int a = qu.poll();
for(int b=0; b<N; b++){
if(map[a][b] != 0 && nodes[a] + map[a][b] < nodes[b]){
nodes[b] = nodes[a] + map[a][b];
qu.add(b);
}
}
}
int answer = 0;
for(int i=0; i<N; i++){
if(nodes[i] <= K) answer++;
}
return answer;
}
}
문제 출처 : Programmers