C++で2つの領域を共に含む最小の共通領域を求めるアルゴリズム

問題の概要

複数のリストからなる領域データを考えてみましょう。各リストの先頭にある領域は、そのリストに含まれる他のすべての領域を包含しています。つまり、領域Xが別の領域Yを含む場合、XはYよりも大きな領域であると定義されます。また、定義上、あらゆる領域Xは自分自身を常に含むものとします。

このとき、2つの領域r1とr2が与えられたら、両方を同時に含む中で最も小さい領域（最小の共通領域）を見つける必要があります。なお、r1・r2・r3という領域が存在し、r1がr3を含んでいる場合には、r3を含む別の領域r2は存在しないことが保証されています。

例えば、入力が以下のようなデータで、r1 = ‘Quebec’、r2 = ’New York’ であるとします。

[["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]]

‘Quebec’と’New York’の両方を含む領域の中で最も小さいものは “North America” となるため、出力は “North America” になります。

解決のアプローチ

この問題は、木構造における最小共通祖先（LCA: Lowest Common Ancestor）を求める考え方と本質的に同じです。各領域について、それを直接含む領域（親）をマップに記録しておけば、任意の領域から根（例えば “Earth”）へと一方向にたどることができます。

具体的には、次の手順で解きます。

• parent というマップ（連想配列）を作成します。
• i を 0 から r のサイズまで繰り返します。
  • j を 1 から r[i] のサイズまで繰り返し、parent[r[i][j]] := r[i][0] として、各領域の親を登録します。
• chain という集合（set）を作成し、まず x を挿入します。
• x が parent に存在する間、以下を繰り返します。
  • x := parent[x] として親へ移動し、移動先の x を chain に挿入します。
• 次に、y が chain に存在しない間、y := parent[y] として親をたどります。
• chain に見つかった時点の y が最小の共通領域なので、y を返します。

この手法では、x側の経路をすべて集合に記録してから、y側を順に根方向へたどっていくため、最初に一致した地点が必ず「最も深い（＝最小の）共通の祖先」になります。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string findSmallestRegion(vector<vector<string>>& r, string x, string y) {
      map < string, string> parent;
      // 各領域の親（それを含む領域）をマップに登録
      for(int i = 0; i < r.size(); i++){
         for(int j = 1; j < r[i].size(); j++){
            parent[r[i][j]] = r[i][0];
         }
      }
      // x から根までの経路を集合に記録
      set <string> chain;
      chain.insert(x);
      while(parent.find(x)!=parent.end()){
         x = parent[x];
         chain.insert(x);
      }
      // y 側を根方向へたどり、最初に一致した点が答え
      while(chain.find(y)==chain.end()){
         y = parent[y];
      }
      return y;
   }
};
main(){
   vector<vector<string>> v = {
      {"Earth","North America","South America"},
      {"North America","United States","Canada"},
      {"United States","New York","Boston"},  
      {"Canada","Ontario","Quebec"},{"South America","Brazil"}
   };
   Solution ob;
   cout << (ob.findSmallestRegion(v, "Quebec", "New York"));
}

入力

[["Earth","North America","South America"],["North America","United States","Canada"],
["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]]
"Quebec"
"New York"

出力

North America

計算量について

領域の総数を N とすると、親マップの構築に O(N)、経路の探索にも最大で O(N) かかるため、全体の時間計算量は O(N) です。また、マップと集合の分だけメモリを消費するため、空間計算量も O(N) となります。領域の階層構造を一度マップ化してしまえば、以降は任意の2つの領域に対して効率よく最小の共通領域を求められるのがこの手法の利点です。