C++で3次元配列の最小合計パスを求めるアルゴリズムと実装方法

本記事では、3次元配列 cube[length][breadth][height] として表現される立方体（キューブ）が与えられたとき、その中を移動して到達できる「最小合計パス」を計算し、結果を出力する方法を解説します。

パスの移動は、各軸方向（length・breadth・height）にのみ進むことを想定し、動的計画法（DP）を用いて効率的に最小コストを求めます。

入出力の例

まず、具体的な入出力シナリオを見てみましょう。

例1

入力：

int cube[length][breadth][height] = { { {2, 4, 1}, {3, 4, 5}, {9, 8, 7}},
                                      { {5, 3, 2}, {7, 6, 5}, {8, 7, 6}},
                                      { {3, 2, 1}, {4, 3, 2}, {5, 4, 3}}}

出力：

Minimum Sum Path In 3-D Array are: 15

説明： 長さ・幅・高さを持つ立方体が与えられています。開始点から終点までの最小合計パスは、2 + 4 + 1 + 3 + 5 = 15 となります。

例2

入力：

int cube[length][breadth][height] = { { {1, 2}, {7, 8}},
                                      { {3, 5}, {9, 16}}}

出力：

Minimum Sum Path In 3-D Array are: 24

説明： この場合も同様に最小合計パスを計算すると、1 + 2 + 5 + 16 = 24 となります。

アルゴリズムのアプローチ

この問題は、2次元グリッドの最小パス問題を3次元に拡張したものです。以下の手順で解きます。

1. 整数値を持つ3次元配列（立方体）を入力として受け取り、関数 Minimum_SubPath(cube) に渡します。
2. 関数 Minimum_SubPath(cube) の内部では、以下の処理を行います。
   • 立方体と同じサイズのDP配列を作成し、arr[0][0][0] を cube[0][0][0] で初期化します。
   • i を 1 から length までループし、arr[i][0][0] = arr[i-1][0][0] + cube[i][0][0] を設定します（i軸方向の境界線）。
   • j を 1 から breadth までループし、arr[0][j][0] = arr[0][j-1][0] + cube[0][j][0] を設定します（j軸方向の境界線）。
   • k を 1 から height までループし、arr[0][0][k] = arr[0][0][k-1] + cube[0][0][k] を設定します（k軸方向の境界線）。
   • i・j の二重ループで、min_val = Minimum(arr[i-1][j][0], arr[i][j-1][0], INT_MAX) を求め、arr[i][j][0] = min_val + cube[i][j][0] を設定します（ij平面）。
   • i・k の二重ループで、min_val = Minimum(arr[i-1][0][k], arr[i][0][k-1], INT_MAX) を求め、arr[i][0][k] = min_val + cube[i][0][k] を設定します（ik平面）。
   • k・j の二重ループで、min_val = Minimum(arr[0][j][k-1], arr[0][j-1][k], INT_MAX) を求め、arr[0][j][k] = min_val + cube[0][j][k] を設定します（jk平面）。
   • i・j・k の三重ループで、min_val = Minimum(arr[i-1][j][k], arr[i][j-1][k], arr[i][j][k-1]) を求め、arr[i][j][k] = min_val + cube[i][j][k] を設定します（内部領域）。
   • 最後に arr[length-1][breadth-1][height-1] を返します。これが最小合計パスの値です。
3. 関数 Minimum(int a, int b, int c) の内部では、3つの値のうち最小値を返します。
   • a が b より小さい場合：a が c よりも小さければ a を返し、そうでなければ c を返します。
   • a が b 以上の場合：b が c より小さければ b を返し、そうでなければ c を返します。

C++実装例

#include<bits/stdc++.h>
using namespace std;
#define length 3
#define breadth 3
#define height 3

int Minimum(int a, int b, int c){
    if(a < b){
        if(a < c){
            return a;
        }
        else{
            return c;
        }
    }
    else if(b < c){
        return b;
    }
    else{
        return c;
    }
}
int Minimum_SubPath(int cube[][breadth][height]){
    int i, j, k;
    int arr[length][breadth][height];
    arr[0][0][0] = cube[0][0][0];

    for(i = 1; i < length; i++){
        arr[i][0][0] = arr[i-1][0][0] + cube[i][0][0];
    }
    for(j = 1; j < breadth; j++){
        arr[0][j][0] = arr[0][j-1][0] + cube[0][j][0];
    }
    for(k = 1; k < height; k++){
        arr[0][0][k] = arr[0][0][k-1] + cube[0][0][k];
    }
    for(i = 1; i < length; i++){
        for(j = 1; j < breadth; j++){
            int min_val = Minimum(arr[i-1][j][0], arr[i][j-1][0], INT_MAX);
            arr[i][j][0] = min_val + cube[i][j][0];
        }
    }
    for(i = 1; i < length; i++){
        for(k = 1; k < height; k++){
            int min_val = Minimum(arr[i-1][0][k], arr[i][0][k-1], INT_MAX);
            arr[i][0][k] = min_val + cube[i][0][k];
        }
    }
    for(k = 1; k < height; k++){
        for(j = 1; j < breadth; j++){
            int min_val = Minimum(arr[0][j][k-1], arr[0][j-1][k], INT_MAX);
            arr[0][j][k] = min_val + cube[0][j][k];
        }
    }
    for(i = 1; i < length; i++){
        for(j = 1; j < breadth; j++){
            for(k = 1; k < height; k++){
                int min_val = Minimum(arr[i-1][j][k], arr[i][j-1][k], arr[i][j][k-1]);
                arr[i][j][k] = min_val + cube[i][j][k];
            }
        }
    }
    return arr[length-1][breadth-1][height-1];
}
int main(){
    int cube[length][breadth][height] = { { {2, 4, 1}, {3, 4, 5}, {9, 8, 7}},
        { {5, 3, 2}, {7, 6, 5}, {8, 7, 6}},
        { {3, 2, 1}, {4, 3, 2}, {5, 4, 3}}};
    cout<<"Minimum Sum Path In 3-D Array are: "<<Minimum_SubPath(cube);
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

Minimum Sum Path In 3-D Array are: 15

まとめ

このアルゴリズムは動的計画法を用いており、時間計算量は O(length × breadth × height)、空間計算量も同じく O(length × breadth × height) となります。各セルへの最小コストを順次確定させていくことで、立方体の対角の反対側にある終点までの最小合計パスを効率的に求めることができます。