Question

[Java][접근법] 플루이드 탑다운 vs 플루이드 바텀업

이 문제와 관련해 필수적인 MIT 강의

첫 접근법
경로 가중치 sk + ka + kb을 최소로하는 k = [1: N]를 찾아 완전 탐색하면 문제를 해결할 수 있다. 이 때, 모든 정점쌍의 최단 경로를 전처리 해 두면 k 탐색이 편리하다.

그들을 구하려면

"단일 출발점 최단경로 알고리즘"을 N번 반복하거나
"모든 정점쌍 최단경로 알고리즘"을 한 번 수행해 두어야 한다.

문제의 본질

그래프는 DAG가 아닐 수 있다. 따라서 위상정렬을 통한 Relaxation은 불가능하다.
음수 가중치는 없다. 따라서 벨만-포드를 제외하고 다익스트라를 고려할 수 있다.
k=[1: N]을 완전 탐색할 것이다. 그러므로 미리 모든 정점쌍의 최단 경로 가중치를 구해두자.
- 다익스트라를 v번 반복하는 비용 O(v² log v + ve log v) = O(v³logv) // 자바의 PQ는 피보나치 힙이 아니므로
- 그보다 효율적인 O(v³) 플로이드-워셜 알고리즘을 고려할 수 있다.
- 다익스트라를 s, a, b를 출발점으로 하여 3번만 쓰는 경우 더 효율적으로 풀릴 수 있다. O(vlog v + e log v) 이 글은 플로이드-워셜을 쓴다.

플루이드-워셜 점화식

C(k, u, v) = 경로 u→v의 사잇경로에는 오로지 정점 V[1: k]만 쓸 수 있다는 제약을 걸었을 때, 최단 경로 가중치.

선택: V[k]를 사잇경로에 넣지 말까 넣을까?
부분 문제: 문제 V[1:k]는 문제 V[1:k-1]에 의존한다. 즉 prefix 부분 문제이다.
C(k, u, v) = min[ C(k-1, u, v), C(k-1, u, k) + C(k-1, k, v) ] (u ≠ v), 0 (u = v)
C(0, u, v) = w(u, v) // 사잇경로가 없는 경우

탑 다운 접근 (Time Limit Exception)

시간복잡도는 동일하나 v³번의 재귀 호출과 v배 많은 메모리 사용량에 의해 뒤쳐지는 듯 하다.

import java.util.*;

class Solution {
    private static final int MAX = 98765432;
    private int[][][] memo;
    private int[][] weight;

    public int solution(int n, int s, int a, int b, int[][] fares) {
        init(n, fares);

        int answer = MAX;
        for (int k = 1; k <= n; k++) 
            answer = Math.min(answer, 
                              floyd(n, s, k) + floyd(n, k, a) + floyd(n, k, b));
        return answer;
    }


    private int floyd(int k, int u, int v) {
        if (k == 0) return weight[u][v];
        if (u == v) return 0;
        return Math.min(floydDP(k-1, u, v), floydDP(k-1, u, k) + floydDP(k-1, k, v));
    }

    private int floydDP(int k, int u, int v) {
        if (memo[k][u][v] == 0)
            memo[k][u][v] = floyd(k, u, v);
        return memo[k][u][v];
    }

    private void init(int n, int[][] fares) {
        this.memo = new int[n+1][n+1][n+1];
        this.weight = new int[n+1][n+1];

        for (int i = 0; i < weight.length; i++)
            for (int j = 0; j < weight[i].length; j++)
                weight[i][j] = MAX;

        for (int[] edge : fares)
            weight[edge[0]][edge[1]] = weight[edge[1]][edge[0]] = edge[2];
    }
}

복잡도
T(V) = θ(부분 문제 수 * 부분 문제 당 시간 * V) = θ(V³)

바텀 업 접근 (Accepted)

import java.util.*;

class Solution {
    private static final int MAX = 98765432;
    private int[][] memo;

    public int solution(int n, int s, int a, int b, int[][] fares) {
        init(n, fares);

        for (int k = 1; k <= n; k++)
            for (int u = 1; u <= n; u++)
                for (int v = 1; v <= n; v++)
                    memo[u][v] = Math.min(memo[u][v], memo[u][k] + memo[k][v]);

        int answer = MAX;
        for (int k = 1; k <= n; k++) 
            answer = Math.min(answer, memo[s][k] + memo[k][a] + memo[k][b]);
        return answer;
    }

    private void init(int n, int[][] fares) {
        this.memo = new int[n+1][n+1];

        for (int i = 0; i < memo.length; i++)
            for (int j = 0; j < memo[i].length; j++)
                    memo[i][j] = (i == j)? 0 : MAX;

        for (int[] edge : fares)
            memo[edge[0]][edge[1]] = memo[edge[1]][edge[0]] = edge[2];
    }
}

복잡도
T(V) = θ(V³)

레전드

김주환―2024.05.03 22:16

주재빈

2022.7.2 01:28

[Java][접근법] 플루이드 탑다운 vs 플루이드 바텀업

김주환―2024.05.03 22:16

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.