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

🔗 문제 링크

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

😮 문제 해결 방법

최단 거리 알고리즘을 적용하는 것이 문제의 키포인트이다.

모든 도시로부터 출발해 모든 도시로 도착하는 최단 거리를 구해준다. 최단 거리를 구하는 방식은 크게 두가지가 있다. (무방향 양수 그래프 기준)

• 하나의 정점 기준 최단 거리구하기 → 다익스트라 알고리즘 : 모든 도시에 대해 구해야하므로 for문을 통해 모든 최단 거리를 구한다.
• 모든 정점 기준 최단 거리 구하기 → 플로이드 워셜 알고리즘

 

모든 정점에 대한 최단거리를 구하는 알고리즘은 플로이드 워셜을 일반적으로 사용하기 때문에 플로이드 워셜 알고리즘을 통해 문제를 해결한다.

(다익스트라 이용시 시간초과 되는 것 확인!)

 

1. 모든 도착 도시에 대한 최소요금을 구하기 위한 fees 배열 선언 및 도로 초기화
2. 플로이드 워셜 알고리즘 실행
3. 출발 도시인 S에서 각각 A, B에 도달할 수 있는 최초의 최소요금은 합승안하고 각각 간 경우 → fees[s][a] + fees[s][b];
4. 출발 도시인 S에서 합승해 각각의 도시로 간 후 해당 도시에서 내려서 따로 택시타고 간 경우 → fees[s][city] + fees[city][a] + fees[city][b];
5. 3, 4중 최소 요금을구해 리턴

🚩 Java 코드

package com.second.algorithm.programmers;

import java.util.Arrays;

public class Solution_72413_합승_택시_요금 {
    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}};

        int rst = solution(n, s, a, b, fares);
        System.out.println("rst = " + rst);

    }

    private static final int INF = 200 * 100_000;
    private static int solution(int n, int s, int a, int b, int[][] fares) {

        // 요금 배열 초기화
        int[][] fees = new int[n + 1][n + 1];
        for (int city = 1; city <= n; city++) {
            Arrays.fill(fees[city], INF);
            fees[city][city] = 0;
        }

        // 도로 생성
        initFees(n, fares, fees);

        // 플로이드 워셜 알고리즘
        floydWarshall(n, fees);

        // 최소 요금 구하기
        int minFee = fees[s][a] + fees[s][b]; // 최초 합승 안한 경우가 최소

        // 합승한 경우 s에서 출발해 도착할 수 있는 도시에서 다시 각각의 도시로의 최소요금 구한 값과 비교
        for (int city = 1; city <= n; city++) {
            minFee = Math.min(minFee, fees[s][city] + fees[city][a] + fees[city][b]);
        }

        return minFee;
    }

    private static void floydWarshall(int n, int[][] fees) {
        for (int mid = 1; mid <= n; mid++) {
            for (int start = 1; start <= n; start++) {
                for (int end = 1; end <= n; end++) {
                    if (start == end) continue;
                    if (fees[start][end] > fees[start][mid] + fees[mid][end]) {
                        fees[start][end] = fees[start][mid] + fees[mid][end];
                    }
                }
            }
        }
    }

    private static void initFees(int n, int[][] fares, int[][] fees) {
        for (int[] fare : fares) {
            int departure = fare[0];
            int destination = fare[1];
            int fee = fare[2];

            fees[departure][destination] = fee;
            fees[destination][departure] = fee;
        }
    }
}