C++で2次元バイナリ配列の最良集合点（ベストミーティングポイント）を求めるアルゴリズムを解説

この問題では、0と1の値のみを持つ2次元バイナリ配列が与えられます。1はグループメンバーの家を表しています。グループのメンバーは集まって会合を開きたいと考えており、共通の集合場所へ移動する距離の合計を最小化する必要があります。集合場所はどこでも構いませんが、ただし誰かの家であることはできません。

最小距離を求めるためには、「マンハッタン距離」と呼ばれる公式を使用します。2点間の距離は次のように定義されます。

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

概念をより明確にするために、具体例を見てみましょう。

例

入力：
    {10001}
    {00000}
    {00100}
出力：6

説明：この場合、最良の集合点は (0, 2) となり、移動距離の合計は 6（2+2+2）になります。

解法のアプローチ

それでは、この問題に対する解法を考えてみましょう。ここで必要なのは、配列内で1としてマークされたすべての点の中間点を見つけることです。これは、水平方向と垂直方向の中心（中央値）をそれぞれ独立に求めることで実現できます。その後、求めた中間点から、1としてマークされたすべての点までの距離を計算します。

このアプローチが有効な理由は、マンハッタン距離の合計が行方向と列方向で独立に計算でき、1次元の点群に対して距離の合計を最小化する点が中央値になるためです。

アルゴリズム

ステップ1：1としてマークされた点の行位置（垂直方向）と列位置（水平方向）をそれぞれ格納する2つの配列を作成する。
ステップ2：両方の配列の中間位置（中央値）を求め、(midx, midy) を集合点として扱う。
ステップ3：各点から中間点までの距離を計算する。
ステップ4：すべての距離の合計を返す。

実装例

上記のアルゴリズムに基づいて、C++プログラムを作成してみましょう。

#include <bits/stdc++.h>
using namespace std;
#define ROW 3
#define COL 5
int minMeetingDistance(int grid[][COL]) {
    if (ROW == 0 || COL == 0)
        return 0;
    vector<int> vertical;
    vector<int> horizontal;
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (grid[i][j] == 1) {
                vertical.push_back(i);
                horizontal.push_back(j);
            }
        }
    }
    sort(vertical.begin(), vertical.end());
    sort(horizontal.begin(), horizontal.end());
    int size = vertical.size() / 2;
    int midx = vertical[size];
    int midy = horizontal[size];
    int distance = 0;
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++)
            if (grid[i][j] == 1)
                distance += abs(midx - i) + abs(midy - j);
    return distance;
}
int main() {
    int distance[ROW][COL] =
    {{1, 0, 1, 0, 1},
    {0, 0, 0, 1, 0},
    {0, 1, 1, 0, 0}};
    cout<<"The minimum distance travelled to meet is "<<minMeetingDistance(distance);
    return 0;
}

出力

The minimum distance travelled to meet is 11

このプログラムの計算量は O(ROW × COL) であり、配列のサイズに比例した効率で最良の集合点における最小移動距離を求めることができます。