2021 KAKAO BLIND RECRUITMENT : 합승 택시 요금(플로이드 워셜)

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

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

 

// 코드

import java.util.*;
 
class Solution {
    
    static final int INF = 40000000;
    int[][] Dist = new int[200][200];
    
    void floyd(int n) {
        for(int k = 0; k < n; ++k) { // 경유지
            for(int i = 0; i < n; ++i) { // 시작점
                for(int j = 0; j < n; ++j) { // 도착점
                    if(Dist[i][k] + Dist[k][j] < Dist[i][j]) {
                        Dist[i][j] = Dist[i][k] + Dist[k][j];
                    }
                }
            }
        }
    }
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        
        // 초기화
        for(int i=0; i<n; ++i) {
            for(int j=0; j<n; ++j) {
                // 출발점과 도착점이 같으면 : 0
                if(i == j) Dist[i][j] = 0;
                else Dist[i][j] = INF;                
            }
        }
        
        // 그래프 방향성 : X
        for(int[] edge : fares) {            
            // [시작점][도착점] = 비용
            Dist[edge[0]-1][edge[1]-1] = edge[2];    
            // [도착점][시작점] = 비용
            Dist[edge[1]-1][edge[0]-1] = edge[2];
        }
        
        // 플로이드 와샬
        floyd(n);
        
        --s;
        --a;
        --b;
                
        int answer = INF;
        for(int k=0; k<n; ++k) {
            answer = Math.min(answer, (Dist[s][k] + Dist[k][a] + Dist[k][b]));
        }
        return answer;
    }
}