[Programmers]합승 택시 요금

[문제 링크]

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

프로그래머스

[생각 흐름]

플로이드워셜 알고리즘이용

start에서  i까지 같이 가고 i 부터 a,b까지 가는 경로

 

[코드]

import java.util.Arrays;

public class Main {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int arr[][] = new int[n+1][n+1];
        int INF = (int) 1e9;

        //배열 초기화 (자기자신 가는 방법은 0 )
        for (int i = 0; i <= n; i++) {
            Arrays.fill(arr[i], INF);
            arr[i][i]=0;
        }

        for (int i = 0; i < fares.length; i++) {
            int[] temp = fares[i];
            int e1 = temp[0];
            int e2 = temp[1];
            int w = temp[2];
            arr[e1][e2] = arr[e2][e1] = w;
        }

        StringBuilder sb = new StringBuilder();

        //플로이드 워셜
        for (int p = 1; p <= n; p++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    arr[i][j] = Math.min(arr[i][p] + arr[p][j], arr[i][j]);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                if (arr[i][j] == INF)  sb.append("INF ");
                else sb.append(arr[i][j] + " ");
            sb.append("\n");
        }

        System.out.println(sb);
        int answer = arr[s][a]+arr[s][b];
        for(int i=1;i<=n;i++){
            int tempMin = arr[s][i]+arr[i][a]+arr[i][b];
            if(tempMin<=0) continue;
            answer = Math.min(tempMin,answer);
        }
        return answer;
    }

}