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

문제

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

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

문제해결방법

이 문제를 풀기 위해 먼저 Floyd Warshall 알고리즘으로 모든 정점 사이의 최단 거리 fw를 구했다.

그리고 가장 적게 택시 요금을 사용하기 위해 아래와 같이 중간에 거치는 장소 X를 정해서 모든 경우들을 계산해주었다.

S~X 까지의 거리 + X~A 까지의 거리 + X~B 까지의 거리

코드

package Programmers;
 
public class Solution_합승택시요금 {
 
    public static int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        int[][] fw = new int[n+1][n+1];
        for(int i=0; i<fares.length; i++) {
            int[] fare = fares[i];
            fw[fare[0]][fare[1]] = fare[2];
            fw[fare[1]][fare[0]] = fare[2];
        }
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(i==j) fw[i][j] = 0;
                else {
                    if(fw[i][j]==0) fw[i][j] = Integer.MAX_VALUE>>2;
                }
            }
        }
        for(int k=1; k<=n; k++) {
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) {
                    if(fw[i][j]>fw[i][k]+fw[k][j]) fw[i][j]=fw[i][k]+fw[k][j]; 
                }
            }
        }
        answer = Integer.MAX_VALUE;
        for(int i=1; i<=n; i++) {
            answer = Math.min(answer, fw[s][i]+fw[i][a]+fw[i][b]);
        }
        return answer;
    }
    
    public static void main(String[] args) {
        int n = 6;
        int s = 4;
        int a = 6;
        int b = 2;
        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}};
        System.out.println(solution(n, s, a, b, fares));
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.