[프로그래머스#JS] 합승 택시 요금

문제

https://programmers.co.kr/learn/courses/30/lessons/72413

해결

• 노드의 최대 길이가 200 이기 때문에 플로이드 와샬 알고리즘이 가능하다.

 // 결과
0: [0, 63, 41, 10, 24, 25]
1: [63, 0, 22, 66, 46, 48]
2: [41, 22, 0, 51, 24, 26]
3: [10, 66, 51, 0, 34, 35]
4: [24, 46, 24, 34, 0, 2]
5: [25, 48, 26, 35, 2, 0]

• start 지점(4) 에서 공유 지점 + 공유지점 에서 a + 공유지점 에서 b 까지 길이의 최솟값을 구하면 된다.

 answer = Math.min(answer, map[s-1][i] + map[i][a-1] + map[i][b-1]);

코드

function solution(n, s, a, b, fares) {
  // 그래프 세팅
  let map = Array.from(new Array(n), () => new Array(n).fill(Infinity));
  map.forEach((row, idx) => (row[idx] = 0));
  fares.forEach((fare) => {
    const [from, to, cost] = fare;

    map[from - 1][to - 1] = cost;
    map[to - 1][from - 1] = cost;
  });

  // 플로이드 와샬
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (map[i][k] === Infinity) continue;
      for (let j = 0; j < n; j++) {
        if (map[k][j] === Infinity) continue;
        map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
      }
    }
  }

  let answer = Infinity;

  // s - 공유 지점 + 공유 지점 - a + 공유 지점 -b
  for (let i = 0; i < n; i++) {
    answer = Math.min(answer, map[s-1][i] + map[i][a-1] + map[i][b-1]);
  }

  return answer;
}