[프로그래머스] 배달 (JS)

풀이 과정

다익스트라
1. 양방향 연결 상태 배열 생성, 노드까지 가는 최솟값을 저장할 배열 생성
2. DFS
3. 최솟값 배열에 담긴 값보다 현재 노드를 거쳐 우회하는 값이 더 작은 경우 최솟값 갱신
이 경우에만 큐에 담기
4. 최솟값 배열에서 값이 K보다 작은 노드의 수 리턴

처음 코드(틀린 풀이)

function solution(N, road, K) {
  const g = {};
  const times = {};
  for (const [a, b, c] of road) {
    const [key1, key2] = [a + '-' + b, b + '-' + a];
    if (!g[a]) g[a] = [];
    if (!g[b]) g[b] = [];
    g[a].push(b);
    g[b].push(a);

    if (!times[key1]) times[key1] = c;
    if (!times[key2]) times[key2] = c;
    if (times[key1] > c) times[key1] = c;
    if (times[key2] > c) times[key2] = c;
  }

  const visited = {};
  const q = [[1, 0]];
  const set = new Set();
  while (q.length) {
    const [s, t] = q.pop();
    if (visited[s] < t) continue;
    visited[s] = t;
    if (t <= K) set.add(s);
    if (set.size === N) break;
    for (const n of g[s]) {
      q.push([n, t + times[s + '-' + n]]);
    }
  }
  return set.size;
}

어찌어찌 DFS로 했더니 될 듯 말 듯 했다.
27번 테스트 케이스만 시간 초과가 나서 이것저것 해보다가 결국 포기했다.

정답 코드

function solution(N, road, K) {
  const g = Array.from(Array(N + 1), () => []);
  const arr = Array(N + 1).fill(Infinity);

  for (const [a, b, c] of road) {
    g[a].push({ to: b, cost: c });
    g[b].push({ to: a, cost: c });
  }

  const q = [{ to: 1, cost: 0 }];
  arr[1] = 0;
  while (q.length) {
    const { to, cost } = q.pop();
    for (const next of g[to]) {
      const tmp = arr[to] + next.cost;
      if (arr[next.to] < tmp) continue;
      arr[next.to] = tmp;
      q.push(next);
    }
  }

  return arr.filter((c) => c <= K).length;
}

결국 다른 사람의 풀이를 참고했다.

🦾

• 다익스트라 알고리즘
  각 배열에 다음 노드와 가중치를 저장해둔다.
  각 노드까지 도달하는 최솟값 배열을 만든다.
  큐에는 해당 노드까지 가는 최솟값과 우회하는 값 중 작은 값을 담는다.
• Array.from(배열, map 함수)로 초기화된 배열을 더 쉽게 생성할 수 있다는 것도 알게 됐다.