[프로그래머스 / js / 플로이드 워셜 알고리즘] 합승 택시 요금

 

문제

 

택시가 이동 가능한 반경에 있는 n개의 지점과 지점 사이의 이동가능한 택시노선과 예상요금을 나타내는 fares가 주어졌을 때 a,b에 각각 도착해야하는 두 사람이 s에서 출발해 각각의 도착 지점까지 택시를 타고 갈때 최저 예상 택시 요금을 return하도록 solution 함수를 완성해라. (합승은 해도 되고 안해도 됨) 

 

입출력 예

 

 

풀이

처음에 보고 문제가 어렵다고 생각했는데 폴로이드 워셜 알고리즘을 공부하고 나니 쉽게 풀 수 있는 문제였다!

 

플로이드 워셜 알고리즘이란 ? 

모든 노드 간의 최단 거리를 구하는 알고리즘으로 n개의 노드에 대하여 n*n개 배열을 만들어 주어진 정보로 초기화를 시켜주고,

경유지에 따라 값을 갱신시켜주면 된다.

 

합승 택시 요금 문제 풀이를 하면서 더 자세히 알아보자!

이 문제는 최단 거리를 구하는 것이 아니라 최저 택시 요금을 구하는 것이므로 (n+1) * (n+1) 배열을 만들고(노드가 1부터라 헷갈릴까봐 n+1로 해주었다) 안의 값을 fares를 돌며 초기화시켜준다.

  let fees = Array.from({ length: n + 1 }, (a) =>
    Array.from({ length: n + 1 }, (a) => Infinity)
  );
  // 자기 자신으로 이동하는 경우는 0
  for (let i = 1; i < n + 1; i++) {
    fees[i][i] = 0;
  }
  fares.map((a) => {
    fees[a[0]][a[1]] = a[2];
    fees[a[1]][a[0]] = a[2];
  });

 

 

fees 배열이 준비가 됐다면 3중 for문을 돌며 기존에 저장되어 있던 값과 mid(경유지)를 지나는 값을 비교해 갱신시켜준다

  for (let mid = 1; mid < n + 1; mid++) {
    for (let start = 1; start < n + 1; start++) {
      for (let end = 1; end < n + 1; end++) {
        fees[start][end] = Math.min(
          fees[start][end],
          fees[start][mid] + fees[mid][end]
        );
      }
    }
  }

 

이제 모든 노드간의 최저 택시 요금이 fees배열에 저장이 되었다. 우리는 s에서 a,b로 가는 최저 택시요금을 구해야하므로 마찬가지로 경유지를 들르는 값과 저장되어 있는 값을 비교해 갱신시켜가며 값을 구해주면 된다!

  let min = fees[s][a] + fees[s][b];
  for (let mid = 1; mid < n + 1; mid++) {
    let temp = fees[s][mid] + fees[mid][a] + fees[mid][b];
    if (min > temp) min = temp;
  }

min에 최저값이 저장돼 이를 return 해주면 끝XD!