[프로그래머스] [Level3] 합승 택시 요금 JAVA

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

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

[문제]

[풀이]

처음에 두 가지 방법을 떠올렷다.
1. 플로이드 와샬
2. 다익스트라

1번의 경우는 플로이드를 돌려서 모든 정점 i->j 에 대한 최소 거리를 다 구한다음에 
최소거리 cost 를 [S->A비용]+[S->B비용] 으로 초기화 한다. => 각자 따로 택시를 타고 가는 경우
그런다음 정점의 수 만큼 반복문을 돌려서 임의의 정점 i 에대해 거쳐갈 경우 최소값을 계속 갱신시킨다.

 
이렇게 하면 [S->i] 로 먼저 간 다음 [i->A] [i->B] 인 것을 다 구해준걸 갱신하다보면 최소값이 나오기때문.

2번의 경우엔 다익스트라를 3번 쓰는것이다. 
다익스트라의 시간복잡도는 O(nlogn) 인데 이걸 3번 해도 O(3nlogn)=>O(nlogn) 이므로
플로이드 시간복잡도 O(n^3) 보다 여전히 빠르다. 
각 정점 S,A,B 에 대해서 다익스트라를 돌려서 최소값을 다 구한다음에 
1번의 마치막 방법처럼 임의의점 i를 도착지로 한 거리를 다 더해준것 중에 최소값을 찾는것.

소스코드는 플로이드만 올림 
( 시간차이 5배까지 나던데 .. 효율성이 더 엄격했으면 통과하지 못 했을수도 ..)

 

 
import java.util.*;
import java.io.*;
import java.util.stream.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Solution sol = new Solution();
        int[][] fares = {{4, 1, 10}, {3, 5, 24}, {5, 6, 2}, {3, 1, 41}, {5, 1, 24}, {4, 6, 50}, {2, 4, 66}, {2, 3, 22},{1, 6, 25}};
        sol.solution(6,4,6,2,fares);
    }
}
 
class Solution {
    int[][] distance;
    private static final int INF = 10000000;
    public int solution(int n, int s, int a, int b, int[][] fares) {
 
        distance = new int[n+1][n+1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j) distance[i][j]=INF;
 
        for (int[] fare : fares)
            distance[fare[0]][fare[1]]=distance[fare[1]][fare[0]] = fare[2];
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    distance[i][j] = Math.min(distance[i][k] + distance[k][j], distance[i][j]);
 
        int cost = distance[s][a]+distance[s][b];
 
        for(int i=1;i<=n;i++)
            cost = Math.min(cost,distance[s][i]+distance[i][a]+distance[i][b]);
        return cost;
    }
}