이번에 풀어본 문제는
프로그래머스 합승 택시 요금 입니다.

📕 문제 링크

❗️코드

import java.util.*;
class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        int [][] map = new int[n+1][n+1];
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <=n; ++j)
            {
                map[i][j] = 19900001;
            }
            map[i][i] = 0;
        }
        
        for(int i = 0; i < fares.length; ++i)
        {
            map[fares[i][0]][fares[i][1]] = fares[i][2];
            map[fares[i][1]][fares[i][0]] = fares[i][2];
        }
        
        for(int k = 1; k <= n; ++k)
        {
            for(int i = 1; i <= n; ++i)
            {
                for(int j = 1; j <=n; ++j)
                {
                    if(map[i][j] > map[i][k] + map[k][j]) map[i][j] = map[i][k] + map[k][j];
                }
            }
        }
        
        answer = Integer.MAX_VALUE;
        int tmp = 0;
        for(int i = 1; i <= n; ++i)
        {
            tmp = map[s][i] + map[i][a] + map[i][b];
            answer = Math.min(answer,tmp);
        }
        return answer;
    }
}

📝 풀이

먼저 각 정점간의 최소 비용을 플로이드와샬 알고리즘을 활용해 구해줍니다.
마지막으로 시작점 -> 경유지 -> a / b로의 거리 를 더한 결과 중 최솟값을 answer에 저장해주면 해결됩니다.

📜 후기

내일 시험이라 기출문제 복습중입니다. 화이팅!