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

[플로이드-워셜]-합승 택시 요금

프로그래머스

 

문제 설명

두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시 요금 return

• 아예 합승하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승하지 않아도 됨
• 3 ≤ n ≤ 200
• 1 ≤ s, a, b ≤ n

입출력 예시

n	s	a	b	fares	result
6	4	6	2	[[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]]	82
7	3	4	1	[[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]]	14

 

풀이 방법

처음 접근한 방식

‘무지 + 어피치 = 택시 요금을 구하는 것’ 이기 때문에, 우선순위 큐를 이용해서 S에서 A 혹은 B까지의 최단 경로를 구하면서 동시에 그 최단 경로까지 가는 루트를 구하려고 했음

최단 경로까지 가는 루트 중 겹치는 루트를 최종적으로 빼주려고 했음

이러한 접근 방식은 각각의 최단 경로를 구하는 것이기 때문에 최종적으로 발생하는 택시 요금의 최소 값을 제대로 구할 수 없음

⇒ 결국 풀이를 참고하게 됐음…

풀이 참고 방식

이 문제는 S에서 시작해서 어떤 루트를 거쳐서 최종 목적지에 도달하는 최소 비용을 구하는 것이기 때문에, 어떤 루트의 부분을 구하기 위해서는 모든 정점에서 다른 정점까지의 최소 비용을 구하는 알고리즘인 플로이드-워셜 알고리즘을 이용해야 함!

현재 N의 최대가 200이기 때문에, 플로이드-워셜 알고리즘을 사용할 경우의 시간 복잡도는 O($N^3$) = 대략 O($200^3$) = 8000000임

1. 플로이드-워셜 알고리즘을 이용해서 모든 정점에서 다른 모든 정점까지의 최단 경로를 구함
2. 두 가지 방식으로 최소 비용을 구할 수 있음
   1. 서로 따로 택시를 타고 가는 경우 → route[s][a] + route[s][b]
   2. 특정 지점을 경유해서 각자의 목적지로 가는 경우 → route[s][k] + route[k][a] + route[k][b]
3. 두 가지 방식으로 구한 것 중에 최소 값을 찾으면 됨

첫 번째 예시를 이용해 풀어보면,

1. 주어진 fares를 통해 테이블 채우기(연결되지 않은 부분은 INF로 채우기)

2. 플로이드-워셜 알고리즘 이용해서 모든 정점에서 다른 모든 정점까지의 최단 경로 구하기

 

3. 두 가지 방식으로 택시 요금 구하기

3-1) 서로 택시를 따로 타는 경우: route[4][6] + route[4][2] = 35 + 66 = 101

3-2) 특정 루트를 경로해서 각자의 목적지로 가는 경우

• 1번 루트 들렸다 가는 경우: route[4][1] + route[1][6] + route[1][2] = 10 + 25 + 63 = 98
• 2번 루트 들렸다 가는 경우: route[4][2] + route[2][6] + route[2][2] = 66 + 48 + 0 = 114
• 3번 루트 들렸다 가는 경우: route[4][3] + route[3][6] + route[3][2] = 51 + 26 + 22 = 99
• 4번 루트 들렸다 가는 경우: route[4][4] + route[4][6] + route[4][2] = 101 ⇒ 서로 택시를 따로 타는 경우와 동일함
• 5번 루트 들렸다 가는 경우: route[4][5] + route[5][6] + route[5][2] = 34 + 2 + 46 = 82
• 6번 루트 들렸다 가는 경우: route[4][6] + route[6][6] + route[6][2] = 35 + 0 + 48 = 83

코드

import java.util.*;

class Solution {
    static int INF = Integer.MAX_VALUE;
    public int solution(int n, int s, int a, int b, int[][] fares) {
        
        // 모든 정점에서 다른 모든 정점까지의 경로를 구할 테이블 채우기
        int[][] route = new int[n+1][n+1];
        for(int r=1; r<=n; r++) {
            for(int c=1; c<=n; c++) {
                // 본인 정점이면 0으로 설정, 그 외에는 INF로 초기화
                if(r != c) route[r][c] = INF;
            }
        }
        // 연결된 경로 표시
        for(int[] fare : fares) {
            route[fare[0]][fare[1]] = fare[2];
            route[fare[1]][fare[0]] = fare[2];
        }
        
        // 플로이드-워셜 알고리즘 수행
        for(int k=1; k<=n; k++) {
            for(int r=1; r<=n; r++) {
                for(int c=1; c<=n; c++) {
                    if(r == c) continue;
                    if(route[r][k] == INF || route[k][c] == INF) continue;
                    route[r][c] = Math.min(route[r][c], route[r][k] + route[k][c]);
                }
            }
        }
        
        int answer = INF;
        // 서로 각자 가는 경우와 특정 경로를 경유해서 가는 경우 중 최소 비용 구하기
        for(int mid=1; mid<=n; mid++) {
            int cost = route[s][mid] + route[mid][a] + route[mid][b];
            
            answer = Math.min(answer, cost);
        }
        
        
        return answer;
    }
}