[프로그래머스] 배달 (플로이드-워셜 알고리즘 Javascript)

💡 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12978

문제 설명

---

처음에 테스트케이스 2개만 성공해서 힌트를 봤는데 플로이드-워셜 알고리즘을 쓰면 된다고 했다.

플로이드-워셜 알고리즘

플로이드-워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.

위의 그림을 보면 1에서 4로 바로 갈 수 있는 경로가 없지만 중간 노드 2와 5를 거친다면 4로 갈 수 있다.
2를 거쳐가는 경우는 거리가 7이고, 5를 거쳐가는 경우 거리가 -1이기 때문에 1에서 4로 가는 최단 거리는 -1이 된다.

이를 구하는 방법은

1. NxN 배열에(chart) 노드 start에서 end에서 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)으로 초기화 한다.

2. 최단 거리를 구하기 위해 start와 end사이의 모든 노드 mid에 대해 현재 chart[start][end]에 저장되어 있는 값과 chart[start][mid] + chart[mid][end] 값을 비교했을 때 더 작은 값(최단 거리)으로 업데이트 한다.

function floid(chart){
  for (let mid = 0; mid < chart.length; mid++) {
    for (let start = 0; start < chart.length; start++) {
      for (let end = 0; end < chart.length; end++) {
        chart[start][end] = Math.min(chart[start][end], chart[start][mid] + chart[mid][end]);
      }
    }
  }
  return chart;
}

---

풀이 📝

function solution(N, road, K) {
  var graph =  new Array(N).fill().map(()=> new Array(N).fill(Infinity));
  // NxN배열 graph에 Infinity를 넣어서 초기화
  var answer = 0;
    
  for(let i = 0; i < N; i++){
      graph[i][i] = 0;
  } 
  // graph배열에 자기 자신으로 가는 경로를 0으로 넣어줌
  
  for(let i = 0; i < road.length; i++){
        graph[road[i][0]-1][road[i][1]-1] = Math.min(graph[road[i][0]-1][road[i][1]-1],road[i][2]);
        graph[road[i][1]-1][road[i][0]-1] = Math.min(graph[road[i][0]-1][road[i][1]-1],road[i][2]);
  }
  // graph배열에 주어진 경로중 최단 거리를 넣어줌 (3,5,3, 3,5,2 가 있을 때 3->5는 2를 넣어줌)
  
  function floid(chart){
   for (let mid = 0; mid < chart.length; mid++) {
     for (let start = 0; start < chart.length; start++) {
       for (let end = 0; end < chart.length; end++) {
         chart[start][end] = Math.min(chart[start][end], chart[start][mid] + chart[mid][end])
       }
     }
   }
   return chart;
  }
  
  graph = floid(graph);

  for(let i = 0; i < N; i++){
     if(graph[0][i] <= K){ // 1번에서 가는 경로이기 때문에 graph[0]의 원소 중 K이하의 원소의 개수를 세어줌
         answer++;
     }
  }
    
   return answer;
}

다른 사람의 풀이 💯

function solution(N, road, K) {
   const totalDist = new Array(N+1).fill(Infinity);
   const adj = Array.from({length: N+1}, () => []);
   // 인덱스가 0부터 시작이라서 N+1

   road.forEach(([a,b,c]) => {
       adj[a].push({to: b, dist: c})
       adj[b].push({to: a, dist: c})
   })

   const queue = [{to: 1, dist: 0}];
   totalDist[1] = 0;

    while(queue.length) {
        let {to, dist} = queue.pop();

        adj[to].forEach((step) => {
            if (totalDist[step.to] > totalDist[to] + step.dist) {
                totalDist[step.to] = totalDist[to] + step.dist;
                queue.push(step);
            }
        })
    }

    return totalDist.filter((dist) => dist <= K).length;

}

나도 객체랑 forEach 간지나게 쓰고 싶다...