[프로그래머스] 코딩테스트 연습 - 45

level 2 - 배달

마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

입출력 예시
N : 5
road : [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]
K : 3
-> 4

function solution(N, road, K) {
    var answer = 0;
    var route = Array.from(Array(N), () => Array(N).fill(Infinity))
    for (var i=0; i<N; i++) route[i][i] = 0;
    
    road.forEach((r) => {
        if (route[r[0] - 1][r[1] - 1] > r[2]) {
            route[r[0] - 1][r[1] - 1] = r[2]; 
            route[r[1] - 1][r[0] - 1] = r[2]; 
        }
    })
    
    for(var k=0; k<N; k++) {
        for (var i=0; i<N; i++) {
            for (var j=0; j<N; j++) {
                if (route[i][k] + route[k][j] < route[i][j])
                    route[i][j] = route[i][k] + route[k][j];
            }
        }
    }
    
    return answer = route[0].filter((r) => r <= K).length;
}

오랜만에 floyd 최단경로 사용했다.