C++で最大の島を作る：DFSを使った効率的な解法と実装例

問題概要

0と1から構成される2次元グリッドが与えられます。ここで、最大で1つの「0」を「1」に変更できるとします。その変更を行った後の、最も大きな島の面積を求めてください。なお、この問題における「島」とは、上下左右の4方向で隣接して連結された「1」のグループを指します。

例えば、入力が [[1, 0], [0, 1]] の場合、出力は 3 となります。これは、どれか1つの「0」を「1」に変更することで2つの「1」がつながり、面積3の島が形成されるためです。

解決アプローチ

この問題は、DFS（深さ優先探索）を使って各島に一意のIDを割り当て、それぞれの島の面積をあらかじめ記録しておくことで効率よく解くことができます。手順は以下の通りです。

• 4×2のサイズを持つ移動方向の配列 dir を定義します。dir := {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
• idx、i、j、grid を引数に取る関数 dfs() を定義します。
• (i, j) がグリッドの範囲外にある、または grid[i][j] が1ではない場合は、0 を返します。
• ret := 1 とし、grid[i][j] := idx を代入して、このセルに島のIDを書き込みます。
• k := 0 から k < 4 の間、以下を繰り返します。
  • ni := dir[k][0] + i、nj := dir[k][1] + j
  • ret := ret + dfs(grid, ni, nj, idx)
• ret を返します。

mainメソッドでの処理

• ret := 0、idx := 2 で初期化します（0と1は元のマスの値として使われているため、IDは2から開始します）。
• サイズ2の配列 area を定義します（島のIDと配列のインデックスを対応させるためです）。
• n := グリッドの行数、m := グリッドの列数とします。
• i := 0 から n 未満、j := 0 から m 未満まで二重ループで走査し、grid[i][j] が 1 の場合には次を行います。
  • area の末尾に dfs(grid, i, j, idx) の結果を追加します。
  • ret := max(ret, area の末尾の要素)
  • idx を1増やします。
• 再び二重ループでグリッドを走査し、grid[i][j] が 0 の場合には次を行います。
  • セット idxs を定義します。
  • k := 0 から k < 4 の間、ni := i + dir[k][0]、nj := j + dir[k][1] とし、(ni, nj) がグリッドの範囲内かつ grid[ni][nj] が非ゼロであれば、grid[ni][nj] を idxs に挿入します。
  • temp := 1 とします（自分自身のマス分）。
  • idxs 内の全要素 it に対して、temp := temp + area[it] を行います。
  • ret := max(ret, temp)
• ret を返します。

ポイントは、各「0」のマスについて周囲4方向を調べ、隣接する島のIDをセット（重複なし）に集める点です。これにより、同じ島を二重にカウントすることなく、そのマスを「1」に変えた場合の合計面積を正しく計算できます。

それでは、理解を深めるために以下の実装例を見てみましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
    public:
    int dfs(vector<vector<int>>& grid, int i, int j, int idx){
       if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()
       || grid[i][j] != 1) return 0;
       int ret = 1;
       grid[i][j] = idx;
       for(int k = 0; k < 4; k++){
           int ni = dir[k][0] + i;
           int nj = dir[k][1] + j;
           ret += dfs(grid, ni, nj, idx);
       }
       return ret;
    }
    int largestIsland(vector<vector<int>>& grid) {
       int ret = 0;
       int idx = 2;
       vector<int> area(2);
       int n = grid.size();
       int m = grid[0].size();
       for(int i = 0; i < n; i++){
          for(int j = 0; j < m; j++){
             if(grid[i][j] == 1){
                area.push_back(dfs(grid, i, j, idx));
                ret = max(ret, area.back());
                idx++;
             }
          }
       }
       for(int i = 0; i < n; i++){
          for(int j = 0; j < m; j++){
             if(grid[i][j] == 0){
                set<int> idxs;
                for(int k = 0; k < 4; k++){
                   int ni = i + dir[k][0];
                   int nj = j + dir[k][1];
                   if(ni < 0 || nj < 0 || ni >= grid.size() ||
                   nj >= grid[0].size()) continue;
                   if(grid[ni][nj]){
                      idxs.insert(grid[ni][nj]);
                   }
                }
                int temp = 1;
                set<int>::iterator it = idxs.begin();
                while(it != idxs.end()){
                   temp += area[*it];
                   it++;
                }
                ret = max(ret, temp);
             }
          }
       }
       return ret;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{1,0},{0,1}};
    cout << (ob.largestIsland(v));
}

入力

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

出力

3

まとめ

このアルゴリズムでは、まずDFSですべての島をラベリングしながら面積を計算し（O(n×m)）、次に各「0」のマスについて周囲の島のIDを集合にまとめて面積の合計を求めます。島ごとの面積をキャッシュしておくことで、同じ島を何度も数える無駄がなくなり、全体の計算量は O(n²×m²) ではなく O(n×m) 程度で抑えられます。0が1つも存在しないケースでも、最初のDFSの段階で最大の島の面積が ret に記録されているため、正しく答えが得られる点にも注目してください。