[Programmers] 배달

sunriseGong·2021년 11월 6일

문제

https://programmers.co.kr/learn/courses/30/lessons/12978?language=javascript

다른 사람 풀이

function solution(N, road, K) {

    const dist = Array(N + 1).fill(Infinity);
    dist[1] = 0;

    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 }]; // 우선순위 큐 배열

    while (pq.length) {

        let { to, time } = pq.pop(); // 우선순위 큐의 마지막 요소 추출

        adj[to].forEach(next => { 
            if (dist[next.to] > dist[to] + next.time) { 
                dist[next.to] = dist[to] + next.time;
                pq.push(next); 
            }
        })
    }
        return dist.filter((item) => item <= K).length;
}

노가다로 이해해보자

N = 6
road = [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]];
K = 4;

1과 나머지 숫자의 최단거리를 모두 구하기

dist

1 과 나머지 마을간의 최소거리를 갱신해나갈 배열
dist : [Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]

1번 인덱스를 1번 마을로 치기 위해서
마을의 수(N) + 1 로 배열을 생성한다.

dist[1] = 0

1 자신과의 거리는 0 이므로
dist : [Infinity, 0, Infinity, Infinity, Infinity, Infinity, Infinity]

adj

각 마을별로 연결된 마을과 거리(road)를 정리한 2차원 배열
각 인덱스가 마을에 해당한다.

road : [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]]
를 순회해 아래처럼 정리 합니다.

adj[0] : []
adj[1] : [{to: 2, time: 1}, {to: 3, time: 2}]
adj[2] : [{to: 1, time: 1}, {to: 3, time: 2}]
adj[3] : [{to: 1, time: 2}, {to: 2, time: 2}, {to: 4, time: 3}, {to: 5, time: 2}, {to: 5, time: 3}]
adj[4] : [{to: 3, time: 3}]
adj[5] : [{to: 3, time: 2}, {to: 3, time: 3}, {to: 6, time: 1}]
adj[6] : [{to: 5, time: 1}]

pq

우선순위 큐 배열
pq : [{ to: 1, time: 0 }] 인 이유는
1 과 연결된 마을(adj[1]) 부터 시작하기 위해

while 문

조건문 :
우선순위 큐(pq)의 길이가 0이 될 때까지 실행

{to, time} :
우선순위 큐의 마지막 요소를 제거(pop())하며 구조분해로 추출한다.
(사실 time까지 구조분해할 필요는 없다.)

to : 우선순위 큐에서 제거한 마지막 요소의 마을

adj[to].forEach((next) =>{}) :
adj[to]('to'와 연결된 마을정보(next)를 요소로 가지는 배열)
을 순회한다.

next : to 와 연결된 마을정보 객체
next.to : to 와 연결된 마을
next.time : next.to 와 to 와의 거리

순회하면서 하게되는 작업 :

if (dist[next.to] > dist[to] + next.time)
1에서 to를 경유해서 next.to 까지 도달하는 거리가
1과 next.to 의 기존의 거리값 보다 작다면

다음 두 작업을 실행합니다.

최단거리 갱신
dist[next.to] = dist[to] + next.time;
1 과 next.to 의 기존 거리값(dist[next.to])을
1에서 to를 경유해서 next.to 까지 도달하는 거리로 갱신하고
큐에 갱신된 마을 정보 객체 추가
pq.push(next);
우선순위 큐에 next 객체를 추가합니다.

while 문 로그변화

to : 1
adj[to] : [{to: 2, time: 1}, {to: 3, time: 2}]
pq : [{to: 2, time: 1}, {to: 3, time: 2}]

to : 3
adj[to] : [{to: 1, time: 2}, {to: 2, time: 2}, {to: 4, time: 3}, {to: 5, time: 2}, {to: 5, time: 3}]
pq : [{to: 2, time: 1}, {to: 4, time: 3}, {to: 5, time: 2}]