C++で解く「最適な集合地点」問題：マンハッタン距離の総和を最小化するアルゴリズム

問題の概要

2人以上からなるグループが集まりたいとき、全員の移動距離の合計を最小限に抑えられる場所を求めます。ここでは、0または1の値を持つ2次元グリッドが与えられ、各「1」はグループ内の誰かの家を表しているものとします。距離はマンハッタン距離で計算され、次の式で定義されます。

distance(p1, p2) = |p2.x − p1.x| + |p2.y − p1.y|

入力例

出力例

この場合の出力は 6 になります。行列から、(0,0)、(0,4)、(2,2) の3か所に住む3人がいることが読み取れます。点 (0,2) が理想的な集合地点であり、総移動距離は 2 + 2 + 2 = 6 となり、これが最小値です。

解決のアプローチ

この問題を効率的に解くには、行方向と列方向それぞれについて座標を収集し、中央値（メディアン）の性質を利用します。マンハッタン距離はX軸とY軸を独立して扱えるため、各行・各列の座標をソートし、両端からペアごとに距離を加算していけば答えが得られます。

アルゴリズムの手順

• 配列 v を受け取る関数 get() を定義する
• 配列 v をソートする
• i := 0、j := v のサイズ − 1、ret := 0 で初期化する
• i < j の間、以下を繰り返す：
  • ret := ret + v[j] − v[i]
  • i を1増やし、j を1減らす
• ret を返す

メイン処理での流れ

• 行座標用の配列 row と列座標用の配列 col を定義する
• グリッド全体を走査し、grid[i][j] が非ゼロであれば、i を row へ、j を col へ追加する
• 最後に get(row) + get(col) を返す

なぜ中央値が有効かというと、数直線上の複数の点に対して総距離を最小にする点は必ず中央値になるためです。両端からのペア加算は、実質的にこの中央値までの距離の総和を計算することと等価になっています。

C++による実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        vector<int> row;
        vector<int> col;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j]) {
                    row.push_back(i);
                    col.push_back(j);
                }
            }
        }
        return get(row) + get(col);
    }
    int get(vector <int> v){
        sort(v.begin(), v.end());
        int i = 0;
        int j = v.size() - 1;
        int ret = 0;
        while (i < j) {
            ret += v[j] - v[i];
            i++;
            j--;
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}};
    cout << (ob.minTotalDistance(v));
}

入力

{{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}}

出力

6

計算量について

このアルゴリズムでは、グリッドの走査に O(m×n)、座標のソートに O(k log k)（k は人数）かかるため、全体の時間計算量は O(k log k) となります。空間計算量は O(k) です。全探索に比べて非常に効率的であり、人数が増えても実用的な速度で動作します。