C++で解く「異なる島の数」問題 ― DFSによる島の形状識別アルゴリズム

問題の概要

2次元のバイナリ配列（グリッド）が与えられます。ここでいう「島」とは、1（陸地）が上下左右方向（水平または垂直）に連結されたグループのことです。グリッドの四方の端はすべて水に囲まれているものと仮定できます。このとき、異なる島の数を数えることが課題です。

2つの島が「同じ」であるとみなされるのは、片方を平行移動（回転や反転は含まない）することでもう片方と一致させられる場合です。

たとえば、次のような入力が与えられたとします。

この場合の出力は 3 となります。

解法のアプローチ

この問題は、DFS（深さ優先探索）を使って各島の形状を「移動経路の文字列」として記録し、それを集合に保存することで解けます。こうすることで、平行移動すれば一致する島（＝同じ形状の島）を重複してカウントせずに済みます。

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

• 関数 dfs() を定義します。引数は x, y, grid, temp, c です。

• x または y がグリッドの行・列の範囲外にある場合、または grid[x][y] が 0 の場合は、そのまま return します。

• grid[x][y] := 0 とします（訪問済みマーク）。

• temp := temp + c として、移動方向を表す文字を連結します。

• dfs(x + 1, y, grid, temp, 'r')

• dfs(x − 1, y, grid, temp, 'l')

• dfs(x, y + 1, grid, temp, 'd')

• dfs(x, y − 1, grid, temp, 'u')

• temp := temp + 'b' として、バックトラックの印を連結します。

メイン処理では以下を実行します。

• ret := 0 とし、空の集合 visited を定義します。

• i を 0 からグリッドの行数未満まで、j を 0 から列数未満までループします。

  • grid[i][j] が 0 以外の場合、空文字列 aux を用意し、dfs(i, j, grid, aux, 's') を実行します。

    • aux が visited に存在しなければ、ret を1増やし、aux を visited に挿入します。

• 最後に 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>>& grid, string& temp, char c){
      if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || !grid[x][y])
         return;
      grid[x][y] = 0;
      temp += c;
      dfs(x + 1, y, grid, temp, 'r');
      dfs(x - 1, y, grid, temp, 'l');
      dfs(x, y + 1, grid, temp, 'd');
      dfs(x, y - 1, grid, temp, 'u');
      temp += 'b';
   }
   int numDistinctIslands(vector<vector<int>>& grid) {
      int ret = 0;
      set<string> visited;
      for (int i = 0; i < grid.size(); i++) {
         for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j]) {
               string aux = "";
               dfs(i, j, grid, aux, 's');
               if (!visited.count(aux)) {
                  ret++;
                  visited.insert(aux);
               }
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v =
   {{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}};
   cout<<(ob.numDistinctIslands(v));
}

入力

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

出力

3

ポイント解説

このアルゴリズムの鍵となるのは、移動方向を表す文字（r・l・d・u）に加えて、探索から戻る際に必ず 'b' を連結している点です。このバックトラック記号がないと、形状が異なる島が偶然同じ文字列を生成してしまい、誤って同一の島として扱われる可能性があります。

また、探索開始地点を基準とした相対的な移動経路を記録しているため、平行移動された同じ形の島は必ず同一の文字列になります。これにより「平行移動で一致する島は同一」という条件を自然に満たせるのです。

計算量は O(R × C) です。各セルは高々1回しか訪問されず、形状文字列の生成と集合への挿入も全体として効率的に処理されます。