프로그래머스 - 배달

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 배달

https://programmers.co.kr/learn/courses/30/lessons/12978

풀이 : 다익스트라 알고리즘으로 해결

import java.util.*;
class Solution {
    static class Node {
	int i, k;
	public Node(int i, int k) {
		this.i = i;
		this.k = k;
	}
}
    public int solution(int N, int[][] road, int K) {
        int [][] arr = new int [N+1][N+1];
	for(int [] r : road) {
		int a = r[0], b = r[1], c = r[2];
		if(arr[a][b] == 0) arr[a][b] = arr[b][a] = c;
		else arr[a][b] = arr[b][a] = Math.min(arr[a][b], c);
	}
	int [] time = new int [N+1];
	Arrays.fill(time, Integer.MAX_VALUE);
	LinkedList <Node> qu = new LinkedList<Node>();
	qu.add(new Node(1, 0));
	while(!qu.isEmpty()) {
		Node node = qu.poll();
		for (int i = 2; i <= N; i++) {
			if(arr[node.i][i] != 0 && node.k + arr[node.i][i] <= K && time[i] > node.k + arr[node.i][i]) {
				time[i] = node.k + arr[node.i][i];
				qu.add(new Node(i, node.k + arr[node.i][i]));
			}
		}
	}
	int answer = 1;
	for (int i = 2; i <= N; i++) {
		if(time[i] <= K) answer++;
	}
       return answer;
    }
}