C++でエンクレーブ(飛び地)の数を求めるアルゴリズム

問題概要

2次元配列 A が与えられます。各セルは 0(海)または 1(陸)を表しています。ここでの「移動」とは、ある陸のマスから上下左右(4方向)に隣接する別の陸のマスへ歩くこと、あるいはグリッドの境界の外へ出ることを指します。

求めたいのは、「どれだけ移動を繰り返してもグリッドの境界外へ出ることができない」陸のマスの個数です。

例えば、次のようなグリッドが与えられたとします。

この場合、答えは 3 になります。0 に完全に囲まれた 1 が 3 つ存在し、残りの 1 つは境界に接しているため囲まれていないからです。

解法のアプローチ

この問題は DFS(深さ優先探索)を使うことで効率的に解けます。基本的な発想は「境界に接するすべての陸を海(0)に変えてしまい、最後に残った陸の数を数える」というものです。境界からたどり着ける陸は必ず境界外へ出られるため、それらを除外すればよいわけです。

具体的な手順は以下の通りです。

• 方向配列 dir を用意し、[[1,0], [-1,0], [0,1], [0,-1]] を格納します。

• dfs(x, y, A) メソッドを作成します。

• x が負、y が負、x が行数以上、y が列数以上、または A[x][y] が 0 の場合は何もせず return します。

• A[x][y] を 0 に設定します。

• k = 0 から 3 までの各方向について、nx = dir[k][0] + x、ny = dir[k][1] + y として dfs(nx, ny, A) を再帰的に呼び出します。

続いて、メインとなる numEnclaves() メソッドでは以下の処理を行います。

• ret := 0、n := A の行数とします。

• m := n が 0 でなければ A の列数、そうでなければ 0 とします。

• i = 0 から n-1 まで:A[i][0] が 1 なら dfs(i, 0, A) を、A[i][m-1] が 1 なら dfs(i, m-1, A) を呼び出します(左右の端の処理)。

• i = 0 から m-1 まで:A[0][i] が 1 なら dfs(0, i, A) を、A[n-1][i] が 1 なら dfs(n-1, i, A) を呼び出します(上下の端の処理)。

• すべてのセルを走査し、ret に A[i][j] を加算していきます。

• ret を返します。

それでは、実際の実装を見てみましょう。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
   public:
   void dfs(int x, int y, vector < vector <int>>& A){
      if(x < 0 || y < 0 || x >= A.size() || y >= A[0].size() ||
      A[x][y] == 0) return;
      A[x][y] = 0;
      for(int k = 0; k < 4; k++){
         int nx = dir[k][0] + x;
         int ny = dir[k][1] + y;
         dfs(nx, ny, A);
      }
   }
   int numEnclaves(vector<vector<int>>& A) {
      int ret = 0;
      int n = A.size();
      int m = n ? A[0].size() : 0;
      for(int i = 0; i < n; i++){
         if(A[i][0] == 1){
            dfs(i, 0, A);
         }
         if(A[i][m - 1] == 1){
            dfs(i, m - 1, A);
         }
      }
      for(int i = 0; i < m; i++){
         if(A[0][i] == 1){
            dfs(0, i, A);
         }
         if(A[n - 1][i] == 1){
            dfs(n - 1, i, A);
         }
      }
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            ret += A[i][j];
         }
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v1 = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}};
   Solution ob;
   cout << (ob.numEnclaves(v1));
}

入力

[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

出力

3

計算量の評価

• 時間計算量: O(n × m)。各セルは高々一度しか訪問されないためです。

• 空間計算量: O(n × m)。最悪の場合、再帰呼び出しのスタックがグリッド全体の深さに達する可能性があります。