[프로그래머스/JS] Lv2. 배달

문제 링크

---

 

프로그래머스

 

 

조건

---

• a와 b를 잇는 도로가 여러 개 있을 수 있다. 

 

 

문제 풀이

---

1. 노드별 거리를 무한으로 하는 배열 생성(1부터 사용하기 위해 N+1의 배열 생성)

2. 인접한 노드별 가중치의 정보를 담고 있는 배열 생성

3. 인접한 노드별 가중치의 정보를 담고 있는 배열에 데이터 추가

4. 1번 마을에서부터 우선순위 큐 시작 및 초기값 0 할당

5. 우선순위 큐 배열에 값이 없을 때까지 반복

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

7. K 이하의 시간에 배달되는 값 filter

 

 

정답 코드

---

function solution(N, road, K) {
  const dist = Array(N + 1).fill(Infinity); // 1. 노드별 거리를 무한으로 하는 배열 생성
  const adj = Array.from({ length: N + 1 }, () => []); // 2. 인접한 노드별 가중치의 정보를 담고 있는 배열 생성

  // 3. 인접한 노드별 가중치의 정보를 담고 있는 배열에 데이터 추가
  road.forEach(([a, b, c]) => {
    adj[a].push({ to: b, time: c });
    adj[b].push({ to: a, time: c });
  });

  // 4. 1번 마을에서부터 우선순위 큐 시작 및 초기값 0 할당
  const pq = [{ to: 1, time: 0 }];
  dist[1] = 0;

  // 5. 우선순위 큐 배열에 값이 없을 때까지 반복
  while (pq.length) {
    let { to, time } = pq.pop();
    // 6. 연결된 노드에서의 값이 현재의 값 + 해당 노드의 가중치보다 클 경우, 값을 대체하고 우선순위 큐에 데이터 추가
    adj[to].forEach((next) => {
      if (dist[next.to] > dist[to] + next.time) {
        dist[next.to] = dist[to] + next.time;
        pq.push(next);
      }
    });
  }

  // 7. K이하의 시간에 배달되는 값 filter
  return dist.filter((item) => item <= K).length;
}

 

 

참고자료

---

• tistory

 

---

질문이나 잘못된 점은 댓글로 남겨주세요 :)💖

반응형