【C++】閉じた島（Closed Island）の数を求める ― DFSによる解法と実装

問題概要

0（陸地）と1（水）で構成される2次元グリッドが与えられます。島とは、上下左右の4方向に連結した0の最大のグループのことであり、閉じた島（Closed Island）とは、完全に水（1）に囲まれた島を指します。この記事では、グリッド内に存在する閉じた島の個数をC++で求める方法を解説します。

例として、次のようなグリッドを考えてみましょう。

このときの出力は 2 となります。完全に水に囲まれた島がちょうど2つ存在するためです。

解法のアプローチ：DFS（深さ優先探索）

この問題はDFSを用いて解くのが定石です。ポイントは、ある陸地マスから探索を開始した際に、その探索がグリッドの境界の外へ到達してしまうかどうかを判定することです。境界外へ抜けてしまう島は、端まで陸地が続いているということなので、「閉じた島」とは呼べません。

dfsメソッドの手順

1. 島が閉じているかどうかを記録する変数 flag を用意します。
2. dfs(g, i, j, n, m) というメソッドを定義します。
3. i または j がグリッドの範囲外である場合、flag = false として即座に戻ります（境界に到達した＝閉じていないことを意味します）。
4. g[i][j] が 1（水）または -1（訪問済み）の場合は、何もせずに戻ります。
5. g[i][j] が 0（陸地）の場合は、再訪問を防ぐために -1 に書き換えます。
6. 上下左右の4方向に対して、再帰的に dfs を呼び出します。

メイン処理の流れ

1. n × m サイズの dp 行列を作成し、すべて -1 で初期化します。
2. 全セルを走査し、値が 0 の未訪問マスを見つけたら、flag = true に設定してそこから dfs を開始します。
3. dfs 完了後も flag が true のまま残っていれば、その島は一度も境界に触れていない＝閉じた島なので、答えに 1 を加算します。
4. 全マスの走査が終わったら、合計値を返します。

それでは、実際の実装コードを見ていきましょう。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    vector< vector<int> > dp;
    bool flag;
    void dfs(vector<vector<int>>& g, int i, int j, int n, int m){
        if(i>=n || j>=m || i<0 || j<0){
            flag = false;
            return;
        }
        if(g[i][j] == 1 || g[i][j] == -1)return;
        if(g[i][j] == 0)g[i][j] = -1;
        dfs(g, i+1, j, n, m);
        dfs(g, i, j+1, n, m);
        dfs(g, i-1, j, n, m);
        dfs(g, i, j-1, n, m);
    }
    int closedIsland(vector<vector<int>>& g) {
        int ans = 0;
        int n = g.size();
        int m = g[0].size();
        dp = vector< vector<int> >(n, vector<int>(m, -1));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(g[i][j] == 0){
                    flag = true;
                    dfs(g, i, j, n, m);
                    ans += flag;
                }
            }
        }
        return ans;
    }
};
int main(){
    vector<vector<int>> v =
    {{1,1,1,1,1,1,1,0},{1,0,0,0,0,1,1,0},{1,0,1,0,1,1,1,0},{1,0,0,0,0,1,0,1},{1,1,1,1,1,1,1,0}};
    Solution ob;
    cout << (ob.closedIsland(v));
}

入力

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

出力

2

まとめ

このアルゴリズムでは、各セルは高々1回しか訪問されないため、時間計算量は O(n×m)、空間計算量も再帰スタックを含めて O(n×m) となります。境界への到達をフラグで管理するシンプルな発想により、閉じた島だけを正確に数えることができます。同様の手法は「島の数を数える」「島の周囲の長さを求める」など、他のグリッド系問題にも応用できるので、ぜひ覚えておきましょう。