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

안녕하세요. 합승 택시 요금 알고리즘 문제는, 여러 지점 간의 이동 경로를 최적화하는 것 입니다.

문재 개요

택시 합승 문제는 출발지에서 두 명이 출발하여 각자의 목적지까지 가는 최소 택시 요금을 계산합니다. 이 문제는 택시 요금 절약을 위한 최적의 합승 경로를 찾는 것입니다.

 

플로이드-워셜

플로이드-워셜 알고리즘은 모든 쌍 최단 경로 문제를 해결하는 알고리즘으로, 모든 지점에서 다른 모든 지점으로의 최단 경로를 찾습니다. 이 알고리즘은 다이나믹 프로그래밍 기반으로 하며, 그래프의 모든 정점 사이의 최단 거리를 계산합니다.

 

코드

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] dist = new int[n + 1][n + 1];

        // 초기화: 자기 자신으로의 경로는 0, 그 외에는 무한대로 설정
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                } else {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        // fares 배열을 이용하여 각 경로의 요금 설정
        for (int[] fare : fares) {
            dist[fare[0]][fare[1]] = fare[2];
            dist[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++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        // 최적 경로 비용 계산
        int minFare = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            if (dist[s][i] != Integer.MAX_VALUE && dist[i][a] != Integer.MAX_VALUE && dist[i][b] != Integer.MAX_VALUE) {
                minFare = Math.min(minFare, dist[s][i] + dist[i][a] + dist[i][b]);
            }
        }
        return minFare;
    }
}

• 초기화: 무한대값을 'Integer.MAX_VALUE' 로 설정하여, 경로가 존재하지 않는 경우를 표현합니다.
• 요금 테이블 설정 : 주어진 fares 배열을 사용하여 각 지점 간의 요금을 설정합니다.
• 플로이드-워셜 적용 : 모든 정점 쌍에 대해 최단 경로를 계산합니다.
• 최적 경로 계산 : 출발지에서 합승 지점까지, 그리고 각각의 목적지까지의 최소 비용을 계산합니다,

 

성능 분석

• 시간 복잡도 : O(n³) - 플로이드-워셜 알고리즘의 특성상 3중 반복문을 사용합니다.
• 공간 복잡도 : O(n³) - 모든 지점 간의 요금 정보를 저장하기 위해 2차원 배열을 사용합니다.