【C++】DFS（深さ優先探索）を使って2次元マトリクス内の島の数を求める方法

問題の概要

この問題では、0と1のみで構成される2次元のバイナリ行列が与えられます。私たちのタスクは、DFS（深さ優先探索）を用いて、その行列の中にいくつの「島」が存在するかを求めることです。

ここでいう島とは、行列の中で上下左右だけでなく斜め方向にも隣接している、1つ以上の「1」の集まりのことを指します。

具体例で問題を理解しよう

入力 : bin[][] = {{ 1 0 0 0}
  {0 1 0 1}
  {0 0 0 0}
  {0 0 1 0}}
出力 : 3

説明：

この行列には以下の3つの島が存在します。

• bin₀₀ と bin₁₁（斜めに隣接しているため同じ島として扱われる）
• bin₁₃
• bin₃₂

解法のアプローチ

DFSを用いてこの問題を解くには、行列内の各要素について、周囲8方向（上下左右＋斜め4方向）の隣接セルを再帰的に探索し、「1」が連続している領域をひとまとまりとして捉えます。具体的な手順は以下の通りです。

1. すべてのセルを「未訪問」状態にした訪問管理用の配列を用意します。
2. 行列を左上から順に走査し、値が「1」かつ未訪問のセルを見つけたら、そこからDFSを開始します。
3. DFSでは、そのセルから到達可能なすべての連結した「1」を訪問済みとしてマークしていきます。
4. DFSを開始した回数をカウントすれば、それがそのまま島の総数になります。

一度訪問したセルを二度と訪問しないよう管理することで、同じ島を重複してカウントすることを防げます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 4

// 指定されたセルが探索可能かどうかを判定する関数
int canVisit(int bin[][COL], int row, int col, bool visited[][COL]) {
  return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL)
    && (bin[row][col] && !visited[row][col]);
}

// DFSによる探索処理
void DFS(int bin[][COL], int row, int col, bool visited[][COL]) {
  // 周囲8方向への移動量
  static int getNeighbourRow[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
  static int getNeighbourCol[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
  visited[row][col] = true;
  for (int k = 0; k < 8; ++k)
    if (canVisit(bin, row + getNeighbourRow[k], col + getNeighbourCol[k], visited))
      DFS(bin, row + getNeighbourRow[k], col + getNeighbourCol[k], visited);
}

// 島の数を数える関数
int findIslandCount(int bin[][COL]) {
  bool visited[ROW][COL];
  memset(visited, 0, sizeof(visited));
  int islandCount = 0;
  for (int i = 0; i < ROW; ++i)
    for (int j = 0; j < COL; ++j)
      if (bin[i][j] && !visited[i][j]) {
        DFS(bin, i, j, visited);
        islandCount++;
      }
  return islandCount;
}

int main() {
  int bin[][COL] = {{1, 0, 0, 0},
    {0, 1, 0, 1},
    {0, 0, 0, 0},
    {0, 0, 1, 0}};
  cout << "行列に存在する島の数は " << findIslandCount(bin);
  return 0;
}

出力結果

行列に存在する島の数は 3

計算量の分析

時間計算量：O(ROW × COL)。各セルは最大でも1回しか訪問されないためです。

空間計算量：O(ROW × COL)。訪問管理用の配列と、再帰呼び出しのためのスタック領域が必要になるためです。