[프로그래머스] 합승 택시 요금 [플로이드-워셜]

package org.example.알고리즘.합승택시요금;

import java.util.Arrays;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.solution(6, 4, 6, 2,
                new int[][]{{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("================================");
        System.out.println(solution.solution(7, 3, 4, 1,
                new int[][]{{5, 7, 9},
                        {4, 6, 4},
                        {3, 6, 1},
                        {3, 2, 3},
                        {2, 1, 6}}));
        System.out.println("================================");
        System.out.println(solution.solution(6, 4, 5, 6,
                new int[][]{{2, 6, 6},
                        {6, 3, 7},
                        {4, 6, 7},
                        {6, 5, 11},
                        {2, 5, 12},
                        {5, 3, 20},
                        {2, 4, 8},
                        {4, 3, 9}}));
        
    }
    
    //n : 지점의 개수
    //s : 출발지점
    //a : a의 도착지점
    //b : b의 도착지점
    //fares : 택시요금
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        
        //양방향 노드를 만들어야합니다.
        int[][] costs = buildNodes(fares, n);
        
        //플로이드 와샬 알고리즘을 사용합니다.
        /*
         *모든 정점에서 모든 정점으로 가는 최단 경로를 찾는 알고리즘입니다.
         * 단순 bfs 라고 생각할 수 있을 것 같습니니다. 하지만 bfs는 한 정점에서 다른 정점으로 가는 최단 경로를 찾는 알고리즘입니다.
         * 현재 문제는 첫 정점에서 A B 를 거치는 정점까지의 (최소비용) 을 구하는 문제로서
         * 가중치 (택시요금) 이 존재하며
         * 두 명의 승객이 서로 다른 목적지로 가는 여러 경로를 고려해야합니다.
         *
         * bfs로 문제를 해결하는 경우
         * 1. 단일 출발점이라는 제한과
         * 2. 가중치를 처리할 수 없다는 문제
         * 3. 경로의 다양성을 고려할 수 없다는 문제가 발생합니다.
         * */
        for (int mid = 1; mid <= n; mid++) {
            for (int start = 1; start <= n; start++) {
                for (int end = 1; end <= n; end++) {
                    if (costs[start][mid] + costs[mid][end] < costs[start][end]) {
                        costs[start][end] = costs[start][mid] + costs[mid][end];
                    }
                }
            }
        }
        
        //일단  각자 직빵으로 가는 값을 answer 로 선언하고
        answer = costs[s][a] + costs[s][b];
        
        // 어느 경유지를 통과하는 것이 가장 효율적인지를 계산합니다.
        for (int mid = 1; mid <= n; mid++) {
            answer = Math.min(answer, costs[s][mid] + costs[mid][a] + costs[mid][b]);
        }
        
        return answer;
    }
    
    private int[][] buildNodes(int[][] fares, int n) {
        int[][] costs = new int[n + 1][n + 1];
        
        //일단 모든 요소를 최대값으로 설정해야합니다.
        // 그리고 나에게로 가는 비용은 0 으로 설정해야합니다
        for (int i = 1; i <= n; i++) {
            //INTEGER.MAX_VALUE 끼리 만약 더하는 경우 overflow 가 발생합니다. -> 음수값으로 계산될수있기에
            //최댓갑 설정시 중간경유지값이 될수있는 최댓값인 10_0000 * 200 = 2000_0000 을 넘지 않는 값으로 설정해야합니다.
            // 일단 고려하기 귀찮으면 int 값을 더했을시에도 overflow 에서 안전한 1억 값으로 설정해도됨
            
            Arrays.fill(costs[i], 1_0000_0000);
            costs[i][i] = 0;
        }
        
        for (int[] fare : fares) {
            costs[fare[0]][fare[1]] = fare[2];
            costs[fare[1]][fare[0]] = fare[2];
        }
        
        return costs;
    }
    /*엣지 케이스 의 처리
     *
     * S -> A -> B 등의 합승의 택시 최소 비용을 계산해야합니다.
     * 만약 각자 이동의 택시비가 요금이 더 낮다면, 합승할 이유가 없습니다.
     * */
}

• 플로이드 워셜 문제이다.
  • 주석에 추가해놓음

• 플로이드 워셜 설명 gpt

  플로이드 워셜 알고리즘은 그래프 이론에서 모든 쌍 최단 경로 문제를 해결하는 동적 프로그래밍 방식입니다. 이 알고리즘은 그래프 내의 모든 정점 쌍에 대해 최단 경로를 찾는 데 사용됩니다. 여기서 그래프는 정점(vertex)들의 집합과 이 정점들을 연결하는 간선(edge)들의 집합으로 구성되어 있으며, 간선에는 가중치가 있을 수 있습니다.

  • 가중치는..
    • 위 문제에서의 일종의 간선마다의 택시비(가중치) 의 비용을 말합니다.

  플로이드 워셜 알고리즘의 기본 아이디어는 '거쳐 가는 정점'을 기준으로 최단 경로를 갱신하는 것입니다. 즉, 각 정점을 거쳐 가는 모든 경로를 고려하여 두 정점 사이의 최단 거리를 계산합니다.

  알고리즘의 과정은 다음과 같습니다:

  1. 초기화: 그래프의 인접 행렬을 준비합니다. 인접 행렬은 각 정점 간의 가중치를 나타내며, 자기 자신으로의 가중치는 0, 직접 연결된 간선의 가중치는 해당 값, 연결되지 않은 경우는 무한대(또는 매우 큰 수)로 설정합니다.
  2. 알고리즘 실행: 세 개의 중첩된 for 루프를 사용하여 모든 정점 쌍에 대해 최단 거리를 갱신합니다.
     • 첫 번째 루프는 '거쳐 가는 정점' k를 기준으로 합니다.
     • 두 번째 루프는 출발 정점 i를 기준으로 합니다.
     • 세 번째 루프는 도착 정점 j를 기준으로 합니다.
     • 각 단계에서 i에서 j로 가는 현재의 최단 거리와 i에서 k를 거쳐 j로 가는 거리를 비교하여, 더 짧은 거리로 갱신합니다.
  3. 결과: 알고리즘 실행 후, 인접 행렬은 각 정점 쌍 사이의 최단 거리를 나타내는 최단 경로 행렬로 변환됩니다.

  플로이드 워셜 알고리즘의 시간 복잡도는 O(n^3)입니다, 여기서 n은 그래프의 정점 수입니다. 이는 모든 정점 쌍에 대해 최단 거리를 계산하기 때문에 발생하는 복잡도입니다. 이 알고리즘은 그래프가 밀집되어 있거나 정점 수가 적을 때 효율적입니다.

Uploaded by N2T