[2021 KAKAO BLIND RECRUITMENT] 합승 택시 요금

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72413

이 문제는 플로이드 와샬 알고리즘을 이용하여 풀 수 있습니다. 플로이드 와샬 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘으로 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 다익스트라와 달리 모든 정점에서 모든 정점으로의 최단 경로를 구할 때 사용됩니다. 쉽게 말씀드리자면 플로이드 와샬 알고리즘의 경우 노드와 노드 중간에 거쳐가는 정점이 있을 경우 그 정점으로 기준으로 최단 거리를 구합니다.

이 문제의 경우 합승 후 어느 지점에서 갈라지게 됩니다. 이 지점을 k라고 했을 때 i에서 j까지 이동하는데 드는 최소 비용을 dp[i][j]라고 한다면 answer = Math.min(answer, dp[s][k] + dp[k][a] + dp[k][b])가 됩니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static final int INF = 20000000;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] graph = new int[n+1][n+1];
        Arrays.stream(graph).forEach(x -> Arrays.fill(x,INF));
        
        for(int i=0;i<fares.length;i++){
            int start = fares[i][0];
            int end = fares[i][1];
            int cost = fares[i][2];
            
            graph[start][end] = cost;
            graph[end][start] = cost;
        }
        
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(i==j){
                        graph[i][j] = 0;
                        continue;
                    }
                    
                    graph[i][j] = Math.min(graph[i][j],graph[i][k]+graph[k][j]);
                }
            }
        }
        
        int answer = INF;
        for(int i=1;i<=n;i++){
            answer = Math.min(answer, graph[s][i]+graph[i][a]+graph[i][b]);
        }
        
        return answer;
    }
}