C#で2次元マトリックス内の島の数を数える方法｜DFSアルゴリズムを解説

C#を使用して、2次元グリッド（マトリックス）内に存在する島の数を求める方法を解説します。この問題は「Number of Islands」として知られる定番のアルゴリズム問題で、深さ優先探索（DFS）を活用することで効率的に解くことができます。

アルゴリズムの基本的な考え方

この問題は、以下の手順で解決できます。

1. グリッドの線形走査： 2次元グリッドマップを左上から順番に走査していきます。
2. 陸の検出： ノードに「1」が含まれている場合、そのノードはDFS（深さ優先探索）を開始するルートノードとなります。
3. 訪問済みマーク： DFSの実行中、訪問したすべてのノードを「0」に設定して訪問済みとしてマークします。これにより、同じ島を二重にカウントすることを防ぎます。
4. 島のカウント： DFSを開始したルートノードの数をカウントします。各DFSは1つの島を識別するため、このカウント数がそのまま島の数になります。

C#での実装例

using System;
namespace ConsoleApplication{
   public class Matrix{
      public int PrintNumberOfIslands(char[] grid){
         bool[] visited = new bool[grid.GetLength(0), grid.GetLength(1)];
         int res = 0;
         for (int i = 0; i < grid.GetLength(0); i++){
            for (int j = 0; j < grid.GetLength(1); j++){
               if (grid[i, j] == '1' && !visited[i, j]){
                  DFS(grid, visited, i, j);
                  res++;
               }
            }
         }
         return res;
      }
      public void DFS(char[] grid, bool[] visited, int i, int j){
         if (i < 0 || i >= grid.GetLength(0)) return;
         if (j < 0 || j >= grid.GetLength(1)) return;
         if (grid[i, j] != '1' || visited[i, j]) return;
         visited[i, j] = true;
         DFS(grid, visited, i + 1, j);
         DFS(grid, visited, i - 1, j);
         DFS(grid, visited, i, j + 1);
         DFS(grid, visited, i, j - 1);
      }
   }
   class Program{
      static void Main(string[] args){
         Matrix m = new Matrix();
         char[] mm = { { '1', '1', '1', '1', '0' }, { '1', '1', '0', '1', '0' }, { '1', '1', '0', '0', '0' }, { '0', '0', '0', '0', '1' } };
         Console.WriteLine(m.PrintNumberOfIslands(mm));
      }
   }
}

コードのポイント解説

PrintNumberOfIslandsメソッド： グリッド全体を二重ループで走査し、未訪問の「1」セルを見つけるたびにDFSを呼び出してカウンターを1つずつ増やしていきます。

DFSメソッド： 再帰的に上下左右の4方向へ探索を広げます。グリッドの範囲外・陸以外のセル・すでに訪問済みのセルに到達した場合は即座に処理を終了（return）するため、無駄な探索が発生しません。

実行結果

2

上記の入力グリッドでは、左側に大きな島が1つ、右下に小さな島が1つ存在するため、出力は「2」となります。

計算量について

時間計算量は O(M×N)（M：行数、N：列数）です。各セルは最大でも1回しか訪問されないため、非常に効率的なアルゴリズムと言えます。空間計算量は、訪問管理用の配列と再帰スタックにより、最悪ケースで O(M×N) となります。