[프로그래머스] Lv.3 합승 택시 요금.java

lv.3 합승 택시 요금.java

import java.util.*;

class Solution {
    static final int INF = 987654321;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = INF;
        int dist[][] = new int[n+1][n+1];
        for(int i=0; i<n+1; i++){
            Arrays.fill(dist[i], INF);
        }
        
        for(int i=0; i<fares.length; i++){
            for(int j=0; j<fares[i].length; j++){
                int c = fares[i][0];
                int d = fares[i][1];
                int f = fares[i][2];
                dist[c][d] = f;
                dist[d][c] = f;
            }
        }
        
        
        for(int k=1; k<n+1; k++){
            for(int i=1; i<n+1; i++){
                for(int j=1; j<n+1; j++){
                    if(i==j) dist[i][j] = 0;
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        
        for(int i=1; i<n+1; i++){
            if(dist[s][i] != INF && dist[s][a] != INF && dist[s][b] != INF){
                answer = Math.min(answer, dist[s][i] + dist[i][a] + dist[i][b]);
            }
        }
        
        
        return answer;
    }
}

해당 코드에서는 Floyd-Warshall 알고리즘을 사용하여 풀이하였습니다. 이 알고리즘은 모든 쌍 최단 경로를 구하는 알고리즘으로, dist[i][j] 라는 배열을 만들어 i번 정점에서 j번 정점까지 가는 최소 비용을 저장합니다. 이 때, INF(무한대)로 초기화된 배열을 사용합니다.

그리고, fares 배열에서 각 출발점과 도착점, 그리고 그 사이의 비용을 받아와서 dist 배열에 저장합니다. 이 때, 출발점과 도착점은 양방향 그래프이므로, 양쪽으로 각각 비용을 저장합니다.

그 후, dist 배열을 갱신하는데, Floyd-Warshall 알고리즘의 핵심인 점화식을 이용합니다. i에서 j까지 가는 최소 비용은 i에서 k를 거쳐 j까지 가는 비용과 i에서 j까지 가는 비용 중 작은 값입니다.

마지막으로, s에서 출발하여 각 지점 i를 거쳐 a와 b로 가는 최소 비용을 계산합니다. 이 때, s에서 i까지의 비용과 i에서 a, b까지의 비용을 합한 값 중 가장 작은 값을 찾아서 반환합니다.

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