알고리즘 문제 풀이(프로그래머스 - 배달)

프로그래머스 LEVEL 2(배달)

• 사용 언어 : javascript

• 해결 날짜 : 2022-12-16

• 해결 방법 :

  • 다익스트라 알고리즘을 통해 문제 해결
    • 양방향으로 이동 가능하므로 graph에서 양방향 연결
    • q에 출발 위치와 출발 위치 까지의 거리를 push()
      • q의 초기값으로 1번 노드와 1번 노드까지의 거리(0)을 push()
    • q가 비어있지 않은 동안,
      • graph에서 from과 연결된 노드[to, dist]들에 대해
      • 1번 노드부터 from 까지의 거리(fromCost)와, from부터 to까지의 거리(dist)를 더한 toCost가 현재까지 저장된 to까지의 거리(distance[to])보다 작은 경우
        • distance[to]의 값 업데이트 및 q에 업데이트된 값으로 push()
    • 반복문 종료 후 distance의 값 중 K보다 작거나 같은 값들만 filter() 후 길이 반환

• 회고 :

  • x

• 코드

  function solution(N, road, K) {
    const graph = Array.from({ length: N + 1 }, () => []);
    const distance = Array.from({ length: N + 1 }, () => Infinity);
    distance[1] = 0;
  
    for (const [from, to, d] of road) {
      graph[from].push([to, d]);
      graph[to].push([from, d]);
    }
  
    const q = [[1, distance[1]]];
  
    while (q.length) {
      const [from, fromCost] = q.shift();
  
      for (const [to, dist] of graph[from]) {
        const toCost = fromCost + dist;
  
        if (toCost < distance[to]) {
          distance[to] = toCost;
          q.push([to, toCost]);
        }
      }
    }
  
    return distance.filter((d) => d <= K).length;
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges