[Refresh ! 코딩 테스트 / js] -배달

문제설명

• https://han-joon-hyeok.github.io/posts/dijkstra-algorithm/
  나의 코드 분의 코드를 보면서 알고리즘을 공부함
• 사실 heap 을 구현해야 시간오류가 안날거 같은데 구현하기 귀찮아서 다른 사람들 보니까 그냥 bfs + 다익스트라 알고리즘을 섞어서 품
• bfs 을 해도 왜 될까? 생각해보니. 주변 이웃이 이전에 갔던곳 보다 크다면 굳이 안가도 됨.. 이 법칙을 따랐기 때문에 bfs 로도 풀렸다고 생각함
• 2중 Array 만드는 부분에서 계속 오류나서 왜지?? 싶었는데 내가 만든거는 그냥 Array.from {length: n } ,()=>[]) 이런식으로 빈배열을 만들어달라고 했는데 이부분이 틀린거 였다.

나의 코드

function solution(N, road, K) {
    var answer = 0;

    // bfs 형태인 다이스탁 알고리즘을 사용한거
    let distance= Array(N+1).fill(Infinity);
    let consider_=Array.from({length:N+1},()=>Array())
    for(var i=0; i<road.length; i++){
    
        const[start,end,distance_between]= road[i];
        consider_[start].push([end,distance_between])
        consider_[end].push([start,distance_between])
        
    }
    let queue=[[1,0]];
    distance[1]=0;
    while(queue.length>0){
        let [start,distance_queue]= queue.shift();
     // 여기서 부터 시작해서 하나식 이동하는데 나+ 새낃의 거리가 원래 값보다 작은 경우에만 업데이트 + queue 에 넣고 진행하기로 하면됨
        for(const [i , go_distance] of consider_[start]){
            // 의 자식들의 합
            const sum_family= distance_queue+ go_distance;
            if(distance[i]>sum_family){
                // 인경우에만 업데이트
                distance[i]=sum_family 
                queue.push([i,sum_family]);
            }
        }
    }
    distance= distance.filter((El,index)=>{
        return El<=K 
    })
    return distance.length;
}

남의 코드

function solution(N, road, K) {
  let graph = Array.from(Array(N + 1), () => Array());
  let distance = Array.from({ length: N + 1 }, () => Infinity);
  let queue = [];

  for (let [a, b, c] of road) {
    graph[a].push([b, c]);
    graph[b].push([a, c]);
  }
 
  queue.push([1, 0]);
  distance[1] = 0;
  while (queue.length) {
    const [point, cost] = queue.shift();
    for (let i = 0; i < graph[point].length; i++) {
      const next = graph[point][i][0];
      const nextcost = graph[point][i][1];

      if (distance[next] > distance[point] + nextcost) {
        distance[next] = distance[point] + nextcost;
        queue.push([next, nextcost]);
      }
    }
  }

  distance = distance.filter((v) => v <= K);
  return distance.length;
}
[출처] [프로그래머스] 배달 (JavaScript)|작성자 임우찬

• while 문을 사용할때 easy code 으로 작성하는방법에 대해서 고민해보기
• 문제를 더 분석해보기 , 어떤 형식으로 풀어야 될까? 무엇을 기준으로 코딩을 하면될지에 대해서도 고민해봐야되겠다.