프로그래머스) 합승 택시 요금(플로이드-워셜)

-문제 사이트

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

프로그래머스

코드

function solution(n, s, a, b, fares) {
  let answer = Infinity;

  const INF = Infinity;
  const graph = Array(n)
    .fill()
    .map(() => Array(n).fill(INF));

  for (let [a, b, c] of fares) {
    graph[a - 1][b - 1] = c;
    graph[b - 1][a - 1] = c;
  }

  for (let i = 0; i < n; i++) {
    graph[i][i] = 0;
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        graph[j][k] = Math.min(graph[j][k], graph[j][i] + graph[i][k]);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    answer = Math.min(
      answer,
      graph[s - 1][i] + graph[i][a - 1] + graph[i][b - 1]
    );
  }

  return answer;
}

풀이 방법

이 문제는 플로이드-워셜 알고리즘을 풀어야 하는 문제이다. 처음에는 그냥 BFS 방식으로 풀었다가 맞추지 못했다. 플로이드-워셜 알고리즘은 학교 수업에서 배웠던 내용인데 1년이 지나고 까먹어서 아쉬웠다. 그리고 문제를 풀면서 Array().fill()을 이용하는 부분을 아직 잘 모르는 것은 반성했다.

그리고 마지막 for문에서 "graph[s - 1][i] + graph[i][a - 1] + graph[i][b - 1]" 이거는 스타트 지점에서 i번째 지점으로 가고 i번째 지점에서 각각 a와 b로 가는 경우를 의미한다.

 

-도움이 된 글

https://school.programmers.co.kr/questions/40447

프로그래머스