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

문제 출처

프로그래머스 lev2 - 배달

나의 풀이

1차시도(21.9/100)

function solution(N, road, K) {
  let tw = new Map();
  for(let i=1; i<=N; i++) tw.set(i, [])

  road.map(v => {
    const [a, b, weight] = v;

    tw.get(a).push([b, weight]);
    tw.get(b).push([a, weight]);
  });

  let dist = [];
  dist[1] = 0;

  for(let cur of tw.keys()) {
    // console.log(cur);
    for(let tmp of tw.get(cur)) {
      const [des, weight] = tmp;
      // console.log(tmp);
      if(cur === 1) dist[des] = weight;

      if(dist[cur] && cur < des) {
        if(dist[des]) {
          dist[des] = Math.min(dist[des], dist[cur] + weight);
        } else dist[des] = dist[cur] + weight;
      }
    }
  }

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

  return answer;
}

2차시도(50/100)

function solution(N, road, K) {
  let tw = new Map();
  for(let i=1; i<=N; i++) tw.set(i, [])

  road.map(v => {
    const [a, b, weight] = v;

    tw.get(a).push([b, weight]);
    tw.get(b).push([a, weight]);
  });

  let dist = Array.from({length:N+1}, () => Number.MAX_SAFE_INTEGER);
  dist[1] = 0;

  // console.log(tw);

  for(const cur of tw.keys()) {
    // console.log(cur);
    for(const tmp of tw.get(cur)) {
      const [des, weight] = tmp;

      if(cur === 1 && des !== 1) dist[des] = Math.min(dist[des], weight);
      if(des === 1 && cur !== 1) dist[cur] = Math.min(dist[cur], weight);

      else if(cur !== 1 && des !== 1){
        dist[des] = Math.min(dist[des], dist[cur] + weight);
        dist[cur] = Math.min(dist[cur], dist[des] + weight);
      }
      // console.log(tmp);
      // console.log(dist);
    }
  }

  // console.log(dist)

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

  return answer;
}

3차시도(56.3/100)

단순히 for 전진으로 진행하면 앞쪽에서 제대로 계산되지 않은 부분이 생기므로 while문으로 꼼꼼히 해야 할 것 같은데..

function solution(N, road, K) {
  let tw = new Map();
  for(let i=1; i<=N; i++) tw.set(i, [])

  road.map(v => {
    const [a, b, weight] = v;

    tw.get(a).push([b, weight]);
    tw.get(b).push([a, weight]);
  });

  let dist = Array.from({length:N+1}, () => Number.MAX_SAFE_INTEGER);
  dist[0] = 0;
  dist[1] = 0;

  // console.log(tw);
  let sum = dist.reduce((a,b) => a+b);
  while(sum > Number.MAX_SAFE_INTEGER) {
    for(const cur of tw.keys()) {
      // console.log(cur);
      for(const tmp of tw.get(cur)) {
        const [des, weight] = tmp;
  
        if(cur === 1 && des !== 1) dist[des] = Math.min(dist[des], weight);
        if(des === 1 && cur !== 1) dist[cur] = Math.min(dist[cur], weight);
  
        else if(cur !== 1 && des !== 1){
          dist[des] = Math.min(dist[des], dist[cur] + weight);
          dist[cur] = Math.min(dist[cur], dist[des] + weight);
        }
        // console.log(tmp);
        // console.log(dist);
      }
    }
    sum = dist.reduce((a,b) => a+b);
  }
  // console.log(dist)
  let answer = 0;
  for(let i=1; i<dist.length; i++) {
    if (dist[i] <= K) answer++;
  }

  return answer;
}

4차시도(통과)

경로 계산에서 누락되는 부분이 계속 발생하는 것 같아서 완전탐색을 해야 한다고 판단했다. 그중 BFS를 택했다. (정점들이 다층적으로 깊게 연결되어 있기 보다는 하나의 정점에 여러 개가 연결되어 있는 느낌이라서.. 깊게 들어가는 것보다는 넓게 들어가는 형태가 적합하다고 생각했다)
⇒
최단거리를 찾으려면 현재 계층에서 최대한 훑어보는 bfs가 적합해 보이고,
최대값을 찾으려면 계층을 깊게 들어가서 판단해보는 dfs가 더 어울리는 것 같기도 하고...이건 잘 모르겠다..

dist의 초기값은 Number.MAX_SAFE_INTEGER이므로
if(dist[des] > dist[b] + weight)는 무조건 1회 이상은 발생한다. 이외 상황에서는 굳이 가지를 뻗어나갈 필요가 없고 최단경로에 대해서만 가지를 뻗어나가면 된다.

Dijkstra
Floyd-Warshall

function solution(N, road, K) {
  let tw = new Map();
  for(let i=1; i<=N; i++) tw.set(i, [])

  road.map(v => {
    const [a, b, weight] = v;

    tw.get(a).push([b, weight]);
    tw.get(b).push([a, weight]);
  });

  let dist = Array.from({length:N+1}, () => Number.MAX_SAFE_INTEGER);
  
  const queue = [[1, 0]];
  dist[1] = 0;
  console.log(tw);

  while(queue.length) {
    console.log(queue);
    let [b, _] = queue.pop();

    tw.get(b).map(el => {
      let [des, weight] = el;

      if(dist[des] > dist[b] + weight) {
        dist[des] = dist[b] + weight;
        queue.push(el);
      }
    })
  }
  // console.log(dist);
  return dist.filter(el => el <= K).length;
}

console.log(solution(6, [
  [1, 2, 1], 
  [1, 3, 2], 
  [2, 3, 2], 
  [3, 4, 3], 
  [3, 5, 2], 
  [3, 5, 3], 
  [5, 6, 1]], 4)) // 4