Programmers 합승 택시 요금

 

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

프로그래머스

 

플로이드-와샬 알고리즘을 사용하여 풀이가 가능하다.

 

플로이드-와샬

---

임의의 양의 가중치가 있는 graph의 노드 s에서 e까지 가는 길에 m이라는 경유지가 있다고 할 때, 해당 경로의 최단거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 노드 s에서 e까지 가는 길의 최소값만 구하는 알고리즘이다. 다익스트라는 모든 경로를 하나씩 확인하면서 최소값에 대해서 계속 탐색하는 알고리즘이라면, 플로이드-와샬은 시작 노드와 마지막 노드의 최소 거리만을 사용하여 결과를 낸다.

플로이드-와샬의 시간복잡도는 o(n^3) 이므로 계산이 오래 걸리는 편이다. 문제를 풀이할 때 주어진 조건을 확인하여 시간복잡도를 잘 확인해야 한다.

 

구현

---

플로이드-와샬의 구현은 생각보다 쉽다.

예를 들어 s부터 e까지 가는 최단거리를 d[s][e] 라고 하자. 둘이 직결되어 있으면 d[s][e]에 바로 입력하고, 직결되어 있지 않으면 Infinity 값을 입력하고, 본인에 대한 가중치는 0으로 입력한다. 그 이후 d[s][e] > d[s][m] + d[m][e] 인 경우를 만족한다면, d[s][e] = d[s][m] + d[m][e] 를 실행한다. 직결이 되어 있지 않는 노드의 기본값은 Infinity이지만, 해당 경로가 m을 경유해서 연결이 가능하다면 최소값으로 치환한다.

이 문제는 모든 노드간 최소 거리를 알면 d[s][m] + d[m][a] + d[m][b] 의 최소 거리를 쉽게 구할 수 있다. m에 모든 노드를 대입하여 최소값을 찾으면 된다.

 

/**
 *
 * @param {number} n
 * @param {number} s
 * @param {number} a
 * @param {number} b
 * @param {number[][]} fares
 * @returns {number}
 */
function solution(n, s, a, b, fares) {
  // 전체 노드에 대한 그래프, graph[a][b] 는 a에서 b까지 가는 최단경로라고 생각하자.
  const graph = Array.from({ length: n + 1 }, () =>
    Array.from({ length: n + 1 }).fill(Infinity)
  );
  fares.forEach(([a, b, c]) => {
    // 그래프 제작
    graph[a][b] = c;
    graph[b][a] = c;
  });
  // 본인에 대한 최단경로는 0
  for (let i = 0; i <= n; i++) {
    graph[i][i] = 0;
  }
  // k는 경유, i는 시작, j는 도착
  for (let k = 1; k <= n; k++) {
    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= n; j++) {
        if (graph[i][j] > graph[i][k] + graph[k][j])
          graph[i][j] = graph[i][k] + graph[k][j];
      }
    }
  }
  let answer = Infinity;
  for (let i = 1; i <= n; i++) {
    // 최종적으로 우리의 목표는 s-m + m-a + m-b의 최솟값을 구하는 것이다.
    const shortest = graph[s][i] + graph[i][a] + graph[i][b];
    answer = Math.min(answer, shortest);
  }
  return answer;
}