[프로그래머스] level3 합승 택시 요금 (Java)

문제 링크

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

풀이

1. 접근 방법

문제 분석:

• 무방향 가중치 그래프에서 출발점(S)에서 두 목적지(A, B)까지의 최소 비용을 구해야 함
• 단, 두 사람이 일정 지점까지 함께 이동한 뒤 각각 다른 목적지로 이동하는 방식으로 계산해야 함
• 경로가 합쳐졌다가 갈라지는 지점이 비용 계산의 핵심

알고리즘 선택 과정:

• 다익스트라 알고리즘으로 출발점(S)에서 각각의 목적지(A, B)까지의 최단 거리를 구할 수 있지만, 이 방식은 두 사람이 출발 지점부터 같이 가다가 갈라지는 부분까지의 거리를 중복 계산할 가능성이 생김
• 갈라지는 지점(C)을 기준으로 S에서 C까지의 최단거리, C에서 A까지의 최단거리, C에서 B까지의 최단거리를 각각 더하면 중복 계산을 피할 수 있음
• 모든 정점이 갈라지는 지점(C)이 될 가능성이 있으므로, 모든 정점 간 최단거리를 구할 필요가 있음
  이때 모든 쌍의 최단거리를 구하는 플로이드-와샬 알고리즘을 사용
• 알고리즘의 시간 복잡도는 𝑂(n^3). 문제에서 n≤200으로 제한되어 있으므로 시간 초과가 나지 않음
• 양수 간선만 존재. 사이클이 문제가 되지 않음

2. 의사 코드

arr = 크기 (n+1) x (n+1) 배열로 초기화

// 자기 자신으로 가는 비용은 0, 나머지는 MAX_VALUE
for i in 1부터 n까지:
    for j in 1부터 n까지:
        if i == j:
            arr[i][j] = 0
        else:
            arr[i][j] = INF

// 무방향 그래프 간선 정보 입력
for fare in fares:
    v1, v2, cost = fare
    arr[v1][v2] = min(arr[v1][v2], cost)
    arr[v2][v1] = min(arr[v2][v1], cost)

// 플로이드-와샬
for k in 1부터 n까지:
    for i in 1부터 n까지:
        for j in 1부터 n까지:
        	// i에서 k를 거쳐서 j로 가는 경로가 존재할 때만 갱신
            if arr[i][k] != INF and arr[k][j] != INF:
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])

// 최소 합승 비용 계산
minCost = INF
for i in 1부터 n까지:
	// i에서 s로 가는 경로, i에서 a로 가는 경로, i에서 b로 가는 경로가 모두 존재할 때만 갱신
    if arr[i][s] != INF and arr[i][a] != INF and arr[i][b] != INF:
        minCost = min(minCost, arr[i][s] + arr[i][a] + arr[i][b])

return minCost

3. 시간 복잡도

• 플로이드-와샬 알고리즘이 주요 소요 시간
• O(n^3)
• n은 3 이상 200 이하인 자연수

4. 구현

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;

        int[][] arr = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    continue;
                }
                arr[i][j] = Integer.MAX_VALUE;
            }
        }

        for (int[] fare : fares) {
            int v1 = fare[0];
            int v2 = fare[1];
            int cost = fare[2];

            arr[v1][v2] = Math.min(arr[v1][v2], cost);
            arr[v2][v1] = Math.min(arr[v2][v1], cost);
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j) {
                        continue;
                    }

                    if (arr[i][k] != Integer.MAX_VALUE && arr[k][j] != Integer.MAX_VALUE) {
                        arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
                    }
                }
            }
        }

        int sum = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            if (arr[i][a] == Integer.MAX_VALUE || arr[i][b] == Integer.MAX_VALUE || arr[i][s] == Integer.MAX_VALUE) {
                continue;
            }
            sum = Math.min(sum, arr[i][a] + arr[i][b] + arr[i][s]);
        }

        answer = sum;

        return answer;
    }
}