[프로그래머스] 배달 풀이 / JavaScript

프로그래머스

 

작성 코드 (1차 시도 / 통과)

function solution(n, roads, k) {
    const graph = Array.from({length: n + 1}, () => Array(n + 1).fill(500001))
    for (let i = 1; i <= n; i += 1) graph[i][i] = 0
    roads.forEach(road => {
        const [a, b, c] = road
        graph[a][b] = graph[b][a] = Math.min(graph[a][b], c)
    })
    for (let via = 1; via <= n; via += 1) {
        for (let i = 1; i <= n; i += 1) {
            for (let j = 1; j <= n; j += 1) graph[i][j] = Math.min(graph[i][j], graph[i][via] + graph[via][j])
        }
    }
    let result = 0
    graph[1].forEach(v =>  v <= k ? result += 1 : null)
    return result
}

 

구현 로직 (플로이드 워셜)

이런 문제는 비슷한 유형이 워낙 많아서 대표적으로 다익스트라, 범위가 적은 경우 플로이드 워셜로 해결 가능한 유형입니다. 알고리즘만 이해하고 있다면 5분컷 가능합니다.

 

1. roads의 정보에 따라 각 마을에서 마을로 가는 경로 비용을 graph 2차원 배열에 담기

2. 자신의 마을로는 0을 넣기

3. 마을에서 다른 마을로 가는 비용을 계산. 만약 A에서 C로 가는 비용의 경우 B(via)를 경유해서 가는 비용이 더 적다면 그 값을 새로 갱신.

4. graph의 1번 배열에서 비용이 k이하인 마을의 개수 출력.