(프로그래머스 KAKAO JS)합승 택시 요금

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

코딩테스트 연습 - 합승 택시 요금

 

 

플로이드 와샬을 이용.

 

우선 n + 1 * n + 1의 크기만큼 배열을 선언하여, 이 배열에 요금을 저장한다.

i -> i로 가는 경우의 비용을 0으로 리셋하고, 나머지는 수를 엄청 크게 하여 비용을 갱신하도록 한다.

 

fares에 담겨있는 값을 cost 배열에 저장.(A => B로 가는 비용)

 

플로이드 와샬인 3중 for문을 통해 비용 갱신.

i -> j로 가는 경우와 i -> k -> j로 가는 경우 중 더 싼 비용을 갱신한다.

 

이후, answer 또한 갱신하도록 한다.

현재 비용인 answer과 두 사람이 s에서 출발해 i 까지 합승한 후, i에서 a와 b로 가는 비용을 비교해 더 싼 값을 갱신하면 끝!

const solution = (n, s, a, b, fares) => {
    // answer와 cost를 무조건 크게 만들어서 최소값 찾기
    let answer = 999999999;
    const cost = Array.from({length: n + 1}, () => Array(n + 1).fill(999999999));
    
    // i -> i로 오는 경우는 0으로 리셋
    for(let i = 1; i <= n; i++){
        cost[i][i] = 0;
    }
    
    // A -> B 의 비용 저장
    for(let i = 0; i < fares.length; i++){
        const A = fares[i][0];
        const B = fares[i][1];
        const fare = fares[i][2];
        
        cost[A][B] = fare;
        cost[B][A] = fare;
    }
    
    // 플로이드 와샬
    // i -> j 로 갈 때, i -> k -> j 로 가는 경우의 비용이 더 싼 경우 갱신
    for(let k = 1; k <= n; k++){
        for(let i = 1; i <= n; i++){
            for(let j = 1; j <= n; j++){
                cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
            }
        }
    }
    
    // 두 사람이 i 까지 합승한 후, i에서 각자의 도착지로 가는 비용을 구하여 answer와 비교 및 갱신
    for(let i = 1; i <= n; i++){
        answer = Math.min(answer, cost[s][i] + cost[i][a] + cost[i][b]);
    }
    
    return answer;
}