[JS] 합승 택시 요금

문제

프로그래머스

 

풀이

해당 문제는 출발 지점을 지나 중간 분기점을 거쳐 최종 목표까지 도달할 때 필요한 최소 금액을 구하는 문제이다.

 

하지만 단순히 최소 금액을 도출하는 것이 아닌 두 가지 도착 지점이 있다는 점이 이 문제의 조건에 존재한다.

 

이렇게 특정 비용의 최소 값을 구하는 문제의 경우 다익스라 알고리즘을 사용할 수는 있지만, 해당 문제에서는 효율성 테스트를 진행하고 문제에서 분기점을 거친다는 점도 존재하여 다익스트라 알고리즘에서 파생된 플로이드 위샬 알고리즘을 사용했다.

 

우선 각 지점에서 다른 지점까지 도달할 수 있는 최소 비용을 구해야 한다. 이는 DP를 사용해 각 분기점 별 도달 가능한 지점의 최소값을 구해 문제를 풀이했다.

 

코드

function solution(n, s, a, b, fares) {
  const map = Array.from({ length: n }, () => Array.from({ length: n }, () => Infinity));
  let answer = Infinity;
    
  for (let i = 0; i < n; i++) {
    map[i][i] = 0;
  }
    
  for (let [s, e, v] of fares) {
    map[s - 1][e - 1] = v;
    map[e - 1][s - 1] = v;
  }
    
  // k => 경유
  for (let k = 0; k < n; k++) {
    // i => 출발
    for (let i = 0; i < n; i++) {
      // j => 종점
      for (let j = 0; j < n; j++) {
        if (map[i][k] + map[k][j] < map[i][j]) {
          map[i][j] = map[i][k] + map[k][j];
        }
      }
    }
  }
    
  for (let i = 0; i < n; i++) {
    const temp = map[s - 1][i] + map[i][a - 1] + map[i][b - 1];
    if (answer > temp) answer = temp;
  }
    
  return answer;
}