프로그래머스 - 배달 [ 못품 ]

function solution(N, road, K) {
  const queue = [];
  const adj = Array.from(Array(N + 1), () => new Array());
  const dist = [0, 0];

  for (let i = 0; i < N - 1; ++i) dist.push(Number.MAX_VALUE);

  road.map((info) => {
    let a = info[0];
    let b = info[1];
    let c = info[2];

    adj[a].push({ to: b, weight: c });
    adj[b].push({ to: a, weight: c });
  });

  queue.push({
    to: 1,
    weight: 0,
  });
  console.log(adj);
  console.log(dist);

  while (queue.length) {
    let x = queue.shift();

    adj[x.to].map((a) => {
      if (dist[a.to] > dist[x.to] + a.weight) {
        dist[a.to] = dist[x.to] + a.weight;
        queue.push(a);
      }
    });
  }

  let answer = 0;
  console.log(dist);
  for (let i = 1; i < N + 1; ++i) {
    if (dist[i] <= K) answer++;
  }

  return answer;
}

일단 결과적으로 문제를 해결하지 못하고 구글리을 통해 코드를 가져왔다.

이 코드는 일단 DP를 활용하여 문제를 해결 하였다.

나는 2차원 배열을 통해서 문제를 해결하려고 했지만 해결을 하지 못했고...ㅠㅠ

• 사실 이 부분은 나중에 다시 도전해볼 것이다.

이분 같은 경우에는 queue를 활용하여 문제를 해결하였다.

원래 이러한 문제는 queue를 통해서 해결하는 것이 바람직한 것으로 알고 있다.

• 나도 후에 queue를 적용하여 한번 해결해 보려고 한다.

일단 로직이 정확하게는 잘 이해가 되지 않는다...

dist라는 배열이 DP를 갱신하는 배열이라는 것은 알겠지만 역시나 명시적으로 잘 그려지지가 않는다 ㅠㅠ