🔎 배달

❓ 문제링크

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

📄 제출 코드

function solution(N, road, K) {
    const distance = Array(N + 1).fill(Infinity);
    
    // 빈 배열[]을 N+1개만큼 넣음
    const adj = Array.from({ length: N + 1 }, () => []);

    road.forEach(([a, b, c])=> {
        adj[a].push({ to: b, time: c });
        adj[b].push({ to: a, time: c });
    })

    const pq = [{ to: 1, time: 0 }];
    distance[1] = 0;
    while (pq.length != 0) {
        let { to, time } = pq.pop();

        adj[to].forEach(next => {
            if (distance[next.to] > distance[to] + next.time) {
                distance[next.to] = distance[to] + next.time;
                pq.push(next);
            }
        })
    }
    return distance.filter((item) => item <= K).length;
    
}
let N = 5;
let road = [[1, 2, 1], [2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2]];
let K = 3;
console.log(solution(N, road, K));

처음에 bfs로 풀다가 정답이 틀렸다고 나왔다.
결국 못 풀고 다른사람의 코드를 참고하였다.
가중치를 가진 그래프에서 특정 정점을 시작점으로 나머지 모든 점들에 대한 최단거리를 구한다.

distance : 인접한 노드별 가중치 정보를 가진 배열 생성.
adj : 인접한 노드별 가중치 정보를 담고있는 배열에 데이터 추가

문제에서 1번 마을부터 시작한다고 되있음.
pq를 1번으로 시작 및 초기값 0할당함.

연결된 노드에서 값이 현재값 + 해당노드의 가중치 보다 클 경우 값을 대체하고 우선순위큐에 데이터를 추가한다.

let { to, time } = pq.pop();

adj[to].forEach(next => {
  if (distance[next.to] > distance[to] + next.time) {
    distance[next.to] = distance[to] + next.time;
    pq.push(next);
  }
})

마지막으로 filter를 이용해 K이하 시간의 값들의 갯수를 세어 답을 도출한다.

📘 참고

https://velog.io/@jeky22/javascript-프로그래머스-배달
https://msko.tistory.com/9