알고리즘 문제 풀이(프로그래머스 - 합승 택시 요금)

프로그래머스 LEVEL 3(합승 택시 요금)

• 사용 언어 : javascript

• 해결 날짜 : 2023-01-04

• 해결 방법 :

  • 플로이드 워셜을 통해 문제 해결
    • 무지와 어피치가 같은 택시로 동행하다 중간에 갈라지는 경우도 있으므로 모든 정점에서 다른 모든 정점까지의 최단 거리를 계산해야함
    • node의 개수(n)가 200 이하이므로 3중 for문까지 커버 가능
  • graph에 fares에 담긴 양방향 경로 저장
  • 플로이드 워셜 알고리즘으로 각 정점에서 다른 모든 정점까지의 최단 거리 계산
  • 0부터 n까지 돌며 그래프에 저장된 경로를 탐색
    • 최솟값과 경유지를 거쳤을 때의 최단 경로(graph[s - 1][i] + graph[i][a - 1] + graph[i][b - 1])를 비교후 작은 값으로 update

• 회고 :

  • x

• 코드

  function solution(n, s, a, b, fares) {
    let answer = 0;
    const graph = Array.from({ length: n }, () => Array(n).fill(Infinity));
  
    for (const [from, to, cost] of fares) {
      graph[from - 1][to - 1] = cost;
      graph[to - 1][from - 1] = cost;
    }
  
    for (let i = 0; i < n; i++) {
      graph[i][i] = 0;
      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]);
        }
      }
    }
  
    let min = Infinity;
    for (let i = 0; i < n; i++) {
      min = Math.min(min, graph[s - 1][i] + graph[i][a - 1] + graph[i][b - 1]);
    }
  
    return min;
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges