Lv 3. 합승 택시 요금

 

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

프로그래머스

 

 

 

이 문제는 n개의 정점이 주어지고 각 정점에 번호가 부여되며 s 는 출발지점

a는 a의 집정점, b는 b의집 정점으로 정해졌을때

또한 모든 간선에 음의 가중치가 없을때 

간선의 가중치가 택시비를 의미하고 합승을 제안하기위해 a가 b와 합승할 수 있는

경로와 방법을 찾아 최적의 택시비를 찾는 문제이다.

 

우선 음의 가중치가 없다는 생각에 다익스트라를 구현할 생각이었다.

 

다익스트라는 한 정점에서 모든 정점으로 가는 모든 최단 거리를 구하는것인데

이 다익스트라를 통해 s부터 a  s 부터 b를 더한다면 합승하지 않았을때

택시비를 구할수 있을것 같았다.

 

하지만 여기서 문제가 발생했다.

다익스트라로 구한 s에서 a 까지의 택시비

s에서 b까지의 택시비가 만약 s에서 어느 정점까지가는 경로가 같을때 예를들어 

s -> 1- > 2 -> a 경로이고

s -> 1 -> 3 -> b 경로이면 이는 합승한 것과 다름없지만 합승하지않은 택시비로 계산된다는것

또한 한 정점에서 모든정점으로 가는 최소 택시비 뿐만아니라 각 모든 정점에서 a,b로 가는 

최소택시비 또한 구하여야한다는것을 알았다.

 

결국 다익스트라를 N 번 호출해야하는 문제에 이르렀고 

 

다른 풀이 방법으로 플로이드 워셜을 생각해냈다.

 플로이드 워셜은 모든 정점에서 모든정점으로 가는 최단거리를 구하는 알고리즘이다.

 

이를 통해 모든 정점에서 모든정점으로 가는 최소 택시비를 구해놓는다면 문제를

푸는데는 공식만으로 가능하기에 도전하였다.

 

플로이드 워셜에 대해서 이번 문제를 통해 구현방법을 완벽히 터득한 기분이다.

 

플로이드 워셜을 통해 s에서 a s에서 b 까지의 최소택시비를 모두 구하여 

만약 경로가 겹치지 않았을때 합승하지 않은경우 최소택시비를 구하고

 

이를 경로가 겹쳐 합승하였을때의 최소택시비와 비교하며 

정답을 갱신하였다.

 

 

 

import java.util.*;

class Solution {
    
    int[][] allToAll;
    int INF = Integer.MAX_VALUE;
    
    void floydWarshall(int n){
        for(int i = 1 ; i <= n ; i ++){
            for(int j = 1 ; j <= n ; j++){
                for(int k = 1 ; k <= n ; k++){
                    if(allToAll[j][i] != INF && allToAll[i][k] != INF )
                        allToAll[j][k]=Math.min(allToAll[j][k],allToAll[j][i]+allToAll[i][k]);
                }
            }
        }
    }
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        
        int answer = INF;
        allToAll = new int[n+1][n+1];
                
        //초기화
        for(int i = 0 ; i < n+1 ; i++){
            Arrays.fill(allToAll[i],INF);
            allToAll[i][i] = 0;
        }
        for(int i = 0 ; i < fares.length; i++){
            allToAll[fares[i][0]][fares[i][1]] = fares[i][2];
            allToAll[fares[i][1]][fares[i][0]] = fares[i][2];
        }
        
        floydWarshall(n);
        // 제대로 계산되었다면 여기서 answer은 각각 따로 택시타고 가는 요금이 나옴
        answer = allToAll[s][a] + allToAll[s][b];        
        for(int i = 1 ; i <= n ; i++){
            answer = Math.min(answer,allToAll[s][i]+allToAll[i][a]+allToAll[i][b]);
        }
        return answer;
    }
}