DFSアルゴリズムは5つの島の問題を克服する

DFSアルゴリズムは5つの島の問題を克服する

[[429450]]

この記事はWeChatの公開アカウント「labuladong」から転載したもので、著者はlabuladongです。この記事を転載する場合は、labuladong の公開アカウントにご連絡ください。

島問題は、面接でよく聞かれる古典的な質問です。基本的な島問題は難しくありませんが、サブ島の数や異なる形状の島の数を求めるなど、島問題には興味深い拡張がいくつかあります。この記事では、これらすべての問題を一挙に取り上げます。

島系列問題の核心は、DFS/BFS アルゴリズムを使用して 2 次元配列を走査することです。

この記事では主に、DFS アルゴリズムを使用して島系列問題を数秒で解決する方法について説明します。ただし、BFS アルゴリズムを使用するという中核的な考え方はまったく同じです。DFS を BFS に書き換えるだけです。

では、2 次元マトリックスで DFS 検索を使用するにはどうすればよいでしょうか。2 次元マトリックス内の各位置をノードと見なし、このノードの上下左右の 4 つの位置を隣接ノードと見なすと、マトリックス全体をメッシュのような「グラフ」構造に抽象化できます。

データ構造とアルゴリズムを学習するフレームワーク思考によれば、バイナリツリーのトラバーサルフレームワークに基づいて、2次元行列の DFS コードフレームワークを書き直すことは完全に可能です。

  1.  // バイナリツリートラバーサルフレームワーク
  2. void traverse(TreeNode ルート) {
  3.     トラバース(ルート.左);
  4.     トラバース(ルート.右);
  5.  } 
  6.  
  7.  // 2次元行列走査フレームワーク
  8. void dfs( int [][] グリッド、 int i、 int j、 boolean[] 訪問済み) {
  9.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  10.     i < 0 || j < 0 || i >= m || j >= n の場合 {
  11.         // インデックス範囲外
  12. 戻る;
  13.     }
  14.     （訪問[i][j]）の場合{
  15.         // すでに走査済み (i, j)
  16. 戻る;
  17.     }
  18.     // ノード (i, j) に入る
  19.     訪問[i][j] = true ;
  20.     dfs(grid, i - 1, j); // 上へ
  21.     dfs(grid, i + 1, j); // 次へ
  22.     dfs(grid, i, j - 1); // 左
  23.     dfs(grid, i, j + 1); // 右
  24.     // ノード (i, j) を離れる
  25.     訪問[i][j] = false ;
  26.  }

2次元行列は本質的に「グラフ」であるため、トラバーサルプロセス中に後戻りを防ぐために、訪問済みのブール配列が必要です。上記のコードを理解できれば、すべての島の問題は簡単に解決できます。

2 次元配列を処理するための追加のトリックを次に示します。上、下、左、右のトラバーサルを処理するために「方向配列」が使用されることがありますが、これは前の記事のグラフ トラバーサル フレームワークのコードと非常によく似ています。

  1.  // 方向配列。それぞれ上、下、左、右を表します。
  2.  int [][] dirs = 新しいint [][]{{-1,0}, {1,0}, {0,-1}, {0,1}}; 
  3.  
  4.  void dfs( int [][] グリッド、 int i、 int j、 boolean[] 訪問済み) {
  5.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  6.     i < 0 || j < 0 || i >= m || j >= n の場合 {
  7.         // インデックス範囲外
  8. 戻る;
  9.     }
  10.     （訪問[i][j]）の場合{
  11.         // すでに走査済み (i, j)
  12. 戻る;
  13.     } 
  14.  
  15.     // ノード (i, j) に入る
  16.     訪問[i][j] = true ;
  17.     // 上、下、左、右のノードを再帰的に走査します
  18. for ( int [] d : dirs) {
  19.  int next_i = i + d[0];
  20.  int next_j = j + d[1];
  21.         dfs(グリッド、next_i、next_j);
  22.     }
  23.     // ノード (i, j) を離れる
  24.     訪問[i][j] = false ;
  25.  }

この書き方は、for ループを使用して上下左右のトラバースを処理するだけです。 書き方は個人の好みに応じて選択できます。

島の数

これは、最も単純で最も古典的な島の問題であるパズル「島の数」の200番目の質問です。 質問では、0または1のみを含む2次元配列グリッドを入力する必要があります。0は海水を表し、1は陸地を表し、マトリックスはすべての側面が海水に囲まれていると想定されます。

陸地がつながって島を形成すると言われているので、このマトリックス グリッド内の島の数を計算するアルゴリズムを記述してください。関数のシグネチャは次のとおりです。

  1.  int numIslands( char [][] グリッド);

たとえば、質問で 4 つの島がある次のグリッドが与えられた場合、アルゴリズムは 4 を返す必要があります。

アイデアは非常にシンプルです。鍵となるのは、「島」を見つけてマークする方法です。ここで DFS アルゴリズムが役立ちます。ソリューション コードを直接見てみましょう。

  1.  // メイン関数、島の数を計算する
  2. int numIslands( char [][] グリッド) {
  3. 整数res = 0;
  4.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  5.     // グリッドをトラバースする
  6. ( int i = 0; i < m; i++) {
  7.  ( int j = 0; j < n; j++)の場合{
  8.             グリッド[i][j] == '1'の場合{
  9.                 // 島が発見されるたびに、島の数は1つずつ増えます
  10.                 解像度++;
  11.                 // 次にDFSを使用して島を洪水状態にします
  12.                 dfs(グリッド、i、j);
  13.             }
  14.         }
  15.     }
  16.  resを返します。
  17.  } 
  18.  
  19.  // (i, j) から始めて、隣接するすべての陸地を海水に変えます
  20. void dfs( char [][] グリッド, int i, int j) {
  21.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  22.     i < 0 || j < 0 || i >= m || j >= n の場合 {
  23.         // インデックス範囲外
  24. 戻る;
  25.     }
  26.     グリッド[i][j] == '0'の場合{
  27.         // すでに海水です
  28. 戻る;
  29.     }
  30.     // (i, j) を海水に変換する
  31.     グリッド[i][j] = '0' ;
  32.     // 上、下、左、右の土地を洪水にする
  33.     dfs(グリッド、i + 1、j);
  34.     dfs(グリッド、i、j + 1);
  35.     dfs(グリッド、i - 1、j);
  36.     dfs(グリッド、i、j - 1);
  37.  }

なぜ、島に遭遇するたびに DFS アルゴリズムを使用して島を「洪水」させるのでしょうか。これは主に、トラブルを回避し、訪問した配列の維持を回避するためです。

dfs 関数は、値が 0 の位置に移動すると直接戻るため、渡されたすべての位置が 0 に設定されている限り、戻りません。

PS: このタイプの DFS アルゴリズムは、FloodFill アルゴリズムとも呼ばれます。FloodFill という名前は適切だと思いますか?

この最も基本的な島の問題について私たちが言うべきことはこれだけです。次にどんな話題が出てくるか見てみましょう。

閉鎖された島の数

前回の質問では、2次元マトリックスは海水に囲まれていると考えられるため、端に近い陸地も島とみなされると述べていました。

問題 1254「閉じた島の数を数える」は、次の 2 つの点で前の問題と異なります。

1. 陸地を表すには 0 を使用し、海水を表すには 1 を使用します。

2. 「閉じた島」の数を計算してみましょう。いわゆる「閉じた島」とは、四方を 1 で囲まれた 0 のことです。つまり、端に近い土地は「閉じた島」とはみなされません。

関数のシグネチャは次のとおりです。

  1.  int closedIsland( int [][] グリッド)

たとえば、質問では次の 2 次元行列が入力として与えられます。

アルゴリズムは 2 を返し、画像内の灰色の 0 のみが海水に囲まれた「閉じた島」です。

では、「閉じた島」をどのように特定するのでしょうか。実はとても簡単です。前の質問で端に近い島を除外すると、残ったものが「閉じた島」になるんですよね？

この考えを念頭に置いて、コードを直接見てみましょう。この質問では、0 は陸地を表し、1 は海水を表すと規定されていることに注意してください。

  1.  // メイン関数: 閉じた島の数を計算する
  2. int closedIsland( int [][] グリッド) {
  3.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  4.  ( int j = 0; j < n; j++)の場合{
  5.         // 上の島を洪水にする
  6.         dfs(グリッド, 0, j);
  7.         // 下の島を洪水にする
  8.         dfs(グリッド, m - 1, j);
  9.     }
  10.  ( int i = 0; i < m; i++) {
  11.         // 左側の島を洪水にする
  12.         dfs(グリッド, i, 0);
  13.         // 右側の島を洪水にする
  14.         dfs(グリッド、i、n - 1);
  15.     }
  16.     // グリッドを横断すると、残りの島は閉じた島になります
  17. 整数res = 0;
  18.  ( int i = 0; i < m; i++) {
  19.  ( int j = 0; j < n; j++)の場合{
  20.             グリッド[i][j] == 0の場合{
  21.                 解像度++;
  22.                 dfs(グリッド、i、j);
  23.             }
  24.         }
  25.     }
  26.  resを返します。
  27.  } 
  28.  
  29.  // (i, j) から始めて、隣接するすべての陸地を海水に変えます
  30. void dfs( int [][] グリッド、 int i、 int j) {
  31.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  32.     i < 0 || j < 0 || i >= m || j >= n の場合 {
  33. 戻る;
  34.     }
  35.     グリッド[i][j] == 1の場合{
  36.         // すでに海水です
  37. 戻る;
  38.     }
  39.     // (i, j) を海水に変換する
  40.     グリッド[i][j] = 1;
  41.     // 上、下、左、右の土地を洪水にする
  42.     dfs(グリッド、i + 1、j);
  43.     dfs(グリッド、i、j + 1);
  44.     dfs(グリッド、i - 1、j);
  45.     dfs(グリッド、i、j - 1);
  46.  }

事前に付近の陸地が浸水していれば、島は閉鎖島として計算できます。

PS: DFS/BFS アルゴリズムに加えて、Union Find アルゴリズムもこのタイプのアイランド問題に対処するためのオプションの方法です。前回の記事の Union Find アルゴリズムは、同様の問題を解決するために使用されました。

この島の問題の解決法を少し変更すると、質問 1020 の「飛び地の数」の問題を解くことができます。この問題では、閉じた島の数を求めるのではなく、閉じた島の合計面積を求めます。

実際、考え方は同じです。まず、端に近い土地を水没させ、次に残りの土地を数えます。質問 1020 では、1 は土地、0 は海水を表すことに注意してください。

  1.  int numEnclaves( int [][] グリッド) {
  2.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  3.     // 近くの土地を洪水にする
  4. ( int i = 0; i < m; i++) {
  5.         dfs(グリッド, i, 0);
  6.         dfs(グリッド、i、n - 1);
  7.     }
  8.  ( int j = 0; j < n; j++)の場合{
  9.         dfs(グリッド, 0, j);
  10.         dfs(グリッド, m - 1, j);
  11.     } 
  12.  
  13.     // 残りの土地を数える
  14. 整数res = 0;
  15.  ( int i = 0; i < m; i++) {
  16.  ( int j = 0; j < n; j++)の場合{
  17.             グリッド[i][j] == 1の場合{
  18.                 解像度 += 1;
  19.             }
  20.         }
  21.     } 
  22.  
  23.  resを返します。
  24.  } 
  25.  
  26.  // 前回の実装と同様
  27. void dfs( int [][] グリッド、 int i、 int j) {
  28.     // ...
  29.  }

スペースの制限により、具体的なコードは書きません。引き続き他の島の問題を見てみましょう。

島の最大の面積

これはゲーム「島の最大面積」の695番目の質問です。0は海水を表し、1は陸を表します。ここでは島の数を数えるのではなく、最大の島の面積を計算します。関数のシグネチャは次のとおりです。

  1.  int 島の最大面積( int [][] グリッド)

たとえば、質問では次の 2 次元行列が入力として与えられます。

最大の島はオレンジ色の島で、アルゴリズムはその面積を 6 として返します。

この問題の基本的な考え方は、dfs 関数が島を洪水させる一方で、島の面積を記録する方法も見つける必要があることを除いて、前の問題とまったく同じです。

dfs 関数の戻り値を設定すると、毎回浸水した土地の数を記録できます。解決策を直接見てみましょう。

  1.  int 島の最大面積( int [][] グリッド) {
  2.     // 島の最大面積を記録する
  3. 整数res = 0;
  4.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  5.  ( int i = 0; i < m; i++) {
  6.  ( int j = 0; j < n; j++)の場合{
  7.             グリッド[i][j] == 1の場合{
  8.                 //島を水浸しにして島の最大面積を更新する
  9.                 res = Math.max (res,dfs(grid,i,j));
  10.             }
  11.         }
  12.     }
  13.  resを返します。
  14.  } 
  15.  
  16.  // (i, j) に隣接する土地を浸水させ、浸水した土地の面積を返す
  17. int dfs( int [][] グリッド, int i, int j) {
  18.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  19.     i < 0 || j < 0 || i >= m || j >= n の場合 {
  20.         // インデックス範囲外
  21. 0を返します。
  22.     }
  23.     グリッド[i][j] == 0の場合{
  24.         // すでに海水です
  25. 0を返します。
  26.     }
  27.     // (i, j) を海水に変換する
  28.     グリッド[i][j] = 0; 
  29.  
  30.  dfs(グリッド、i + 1、j)を返す
  31.          + dfs(グリッド、i、j + 1)
  32.          + dfs(グリッド, i - 1, j)
  33.          + dfs(グリッド、i、j - 1) + 1;
  34.  }

解決策は前のものと似ているので、あまり説明しません。次の 2 つの島の問題はより技術的なので、詳しく見ていきましょう。

サブアイランドの数

前の質問がテンプレート質問である場合、質問 1905「サブアイランドの数え方」を解くには頭を使う必要があるかもしれません。

この質問の鍵は、サブアイランドをいかに素早く特定するかということです。Union Find アルゴリズムを使用して特定することは間違いなく可能ですが、この記事では DFS アルゴリズムに焦点を当てているため、Union Find アルゴリズムについては詳しく説明しません。

どのような状況でグリッド 2 の島 B がグリッド 1 の島 A のサブ島になることができますか?

島 B のすべての土地が島 A の土地でもある場合、島 B は島 A の子島になります。

逆に、島 B に陸地があり、島 A の対応する位置が海水である場合、島 B は島 A の子島ではありません。

次に、grid2 内のすべての島をトラバースし、サブ島になることができない島を除外し、残りの島をサブ島にします。

この考え方に基づいて、次のコードを直接記述できます。

  1.  int countSubIslands( int [][] グリッド1, int [][] グリッド2) {
  2.  int m = グリッド1.長さ、n = グリッド1[0].長さ;
  3.  ( int i = 0; i < m; i++) {
  4.  ( int j = 0; j < n; j++)の場合{
  5.             グリッド1[i][j] == 0 && グリッド2[i][j] == 1の場合{
  6.                 // この島は間違いなくサブ島ではない、洪水を起こして
  7.                 グリッド2のiとjの配列をdfsで結合します。
  8.             }
  9.         }
  10.     }
  11.     // これでグリッド2の残りの島はサブ島となり、島の数を計算する
  12. 整数res = 0;
  13.  ( int i = 0; i < m; i++) {
  14.  ( int j = 0; j < n; j++)の場合{
  15.             グリッド2[i][j] == 1の場合{
  16.                 解像度++;
  17.                 グリッド2のiとjの配列をdfsで結合します。
  18.             }
  19.         }
  20.     }
  21.  resを返します。
  22.  } 
  23.  
  24.  // (i, j) から始めて、隣接するすべての陸地を海水に変えます
  25. void dfs( int [][] グリッド、 int i、 int j) {
  26.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  27.     i < 0 || j < 0 || i >= m || j >= n の場合 {
  28. 戻る;
  29.     }
  30.     グリッド[i][j] == 0の場合{
  31. 戻る;
  32.     } 
  33.  
  34.     グリッド[i][j] = 0;
  35.     dfs(グリッド、i + 1、j);
  36.     dfs(グリッド、i、j + 1);
  37.     dfs(グリッド、i - 1、j);
  38.     dfs(グリッド、i、j - 1);
  39.  }

この質問の背後にある考え方は、「閉じた島」の数を計算する考え方と多少似ていますが、後者は端に近い島を除外し、前者はサブ島になることができない島を除外する点が異なります。

島の数が異なる

これはこの記事の最後の島の質問です。最後なので、もちろん最も興味深いものです。

問題 694 は「異なる島の数」です。問題は、0 が海水、1 が陸地を表す 2 次元行列を入力することです。今回は、異なる島の数を計算することが求められます。関数のシグネチャは次のとおりです。

  1.  int numDistinctIslands( int [][] グリッド)

たとえば、質問では次の 2 次元行列を入力します。

島は 4 つありますが、左下隅と右上隅の島は同じ形をしているため、合計で 3 つの異なる島があり、アルゴリズムは 3 を返します。

明らかに、2 次元行列内の「島」を文字列などの型に変換する方法を見つけ、次に HashSet などのデータ構造を使用して重複を削除し、最後に異なる島の数を取得する必要があります。

アイランドを文字列に変換する場合、簡単に言えばシリアル化であり、シリアル化は簡単に言えばトラバーサルです。バイナリツリーのシリアル化とデシリアル化に関する前回の記事では、バイナリツリーと文字列間の変換について説明しましたが、ここでも同様です。

まず、同じ形状の島の場合、同じ開始点から開始すると、dfs 関数が移動する順序は同じでなければなりません。

トラバーサル順序は再帰関数内でハードコードされており、動的に変更されないためです。

  1.  void dfs( int [][] グリッド、 int i、 int j) {
  2.     // 再帰順序:
  3.     dfs(grid, i - 1, j); // 上へ
  4.     dfs(grid, i + 1, j); // 次へ
  5.     dfs(grid, i, j - 1); // 左
  6.     dfs(grid, i, j + 1); // 右
  7. }

したがって、トラバーサル順序は、下の図の 2 つの島のように、ある意味で島の形状を記述するために使用できます。

それらの走査順序が次のとおりであると仮定します。

下、右、上、元に戻す上、元に戻す右、元に戻す下

1、2、3、4 で上、下、左、右を表し、-1、-2、-3、-4 で上、下、左、右の元に戻すを表す場合、それらの移動順序は次のように表すことができます。

2、4、1、-1、-4、-2

これは、島のシリアル化の結果に相当します。 dfs を使用して島をトラバースするたびに、この数字の文字列が生成され、比較される限り、異なる島の数を計算できます。

この番号を生成するには、dfs 関数を少し変更し、トラバーサル順序を記録するための関数パラメータをいくつか追加する必要があります。

  1.  void dfs( int [][] グリッド、 int i、 int j、 StringBuilder sb、 int dir) {
  2.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  3.     i < 0 || j < 0 || i >= m || j >= n の場合
  4.         || グリッド[i][j] == 0) {
  5. 戻る;
  6.     }
  7.     // トラバーサル位置を事前順序で指定: (i, j) を入力します
  8.     グリッド[i][j] = 0;
  9.     sb.append(dir).append( ',' ); 
  10.  
  11.     dfs(grid, i - 1, j, sb, 1); // 上へ
  12.     dfs(grid, i + 1, j, sb, 2); // 次へ
  13.     dfs(grid, i, j - 1, sb, 3); // 左
  14.     dfs(grid, i, j + 1, sb, 4); // 右
  15.  
  16.     // 後順トラバーサル位置: leave (i, j)
  17.     sb.append(-dir).append( ',' );
  18.  }

dir は方向を記録します。dfs 関数が再帰的に終了した後、sb はトラバーサル順序全体を記録します。実際、これは前のバックトラッキング アルゴリズム コア ルーチンで説明したバックトラッキング アルゴリズム フレームワークです。これらのアルゴリズムはすべて同じであることがわかります。

この dfs 関数を使用すると、簡単に処理できます。最終的なソリューション コードを直接記述できます。

  1.  int numDistinctIslands( int [][] グリッド) {
  2.  int m = グリッドの長さ、n = グリッド[0]の長さ;
  3.     // すべての島のシリアル化結果を記録する
  4.     HashSet<String> アイランド = 新しい HashSet<>();
  5.  ( int i = 0; i < m; i++) {
  6.  ( int j = 0; j < n; j++)の場合{
  7.             グリッド[i][j] == 1の場合{
  8.                 // 島をフラッディングし、島のシリアル化された結果を保存します
  9.                 StringBuilder sb = 新しい StringBuilder();
  10.                 // 初期方向は正確さに影響を与えずに任意に記述できます
  11.                 dfs(グリッド、i、j、sb、666);
  12.                 島を追加します(sb.toString());
  13.             }
  14.         }
  15.     }
  16.     // 異なる島の数
  17. island.size ()を返します。
  18.  }

このようにすれば問題は解決します。最初に dfs 関数を呼び出すときの dir パラメータが任意に記述できるのはなぜか、これは DFS とバックトラック アルゴリズムの微妙な違いに関係しています。グラフ アルゴリズムの基本は前回の記事で書いたので、ここでは詳しく説明しません。

上記は島シリーズ全体の問題の解答です。おそらくほとんどの人は前の問題を解くことができるでしょうが、最後の 2 つの問題はまだ比較的巧妙です。この記事が皆さんのお役に立てば幸いです。

<<:  インタビュアー: 貪欲アルゴリズムとバックトラッキングアルゴリズムについて、どのように理解していますか?応用シナリオ?

>>:  AIのおかげで売上が24%増加しました。このようなAI人材はどこで見つけられるのでしょうか?

ブログ    
ブログ    

推薦する

...

...

機械学習、人工知能、ディープラーニングの関係は何ですか?ついに誰かが明らかにした

「機械学習」、「人工知能」、「ディープラーニング」という 3 つの用語は混同されることが多いですが、...

ディープラーニングと機械学習の違いを理解する

機械学習とディープラーニングの違いは何だろうとよく疑問に思う方は、この記事を読んで、その違いを一般の...

機能テストケース自動生成アルゴリズム ペアワイズ

[[433685]]ペアワイズアルゴリズムとは何ですか?次のテストシナリオの場合:ブラウザ: M、O...

...

自律型ドローン技術の長所と短所を探る

自律型ドローン技術は、業界全体に変革をもたらす力として登場し、比類のない効率性と革新性を約束していま...

...

K2 K2、上海交通大学チームが70億パラメータの地球科学言語モデルを発表

地球科学は、岩石、鉱物、土地の特性を研究するだけでなく、地球の気候、海洋、大気、生態系などの現象と原...

...

...

...

座標系の変換を本当に理解していますか?自動運転にはマルチセンサーが不可欠

この記事は、Heart of Autonomous Driving の公開アカウントから許可を得て転...

グーグルは、人工知能の進歩により飛行機による地球温暖化への影響を大幅に軽減できると主張

グーグルは8月14日、飛行機による気候への影響を大幅に軽減できる人工知能の分野で大きな進歩を遂げたと...

Googleは機械学習ベースのDDoS攻撃防御をテスト中

[[412418]] Google Cloud のお客様は、分散型サービス拒否 (DDoS) 保護...