スポンサーリンク

【LeetCode】200. Number of Islands 解答・解説【Python】

スポンサーリンク
スポンサーリンク
この記事は約3分で読めます。

 

 

問題

原文

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Example 2:

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.

 

内容

1は島、0は水を表すm×nの二次元配列のバイナリ配列が与えられます。

島の数を返してください。

島は水に囲われており、隣の島とは縦か横につながっています。

4方向の端より外側は全て水で囲まれています。

 

※正しくない可能性があります。

 

解答

解答1:Python, DFS

 

1つ目の関数でこの問題の解答。2つ目の関数はDFSで隣のマスが島かを判定を行う。

1つ目の関数では、行ごと・列ごとにループを行い、

探索中のマスが”1″、つまり島だった場合に2つめのDFS関数を呼び出す。

 

DFS関数では、最初のif文で探索範囲内であるかを確認している。

・row<0は二次元配列の上端を越えていないか

・row<len(grid)-1は二次元配列の下端を越えていないか

・column<0は二次元配列の左端を越えていないか

・column<len(grid)-1は二次元配列の右端を越えていないか

探索範囲内であれば、現在探索中の島を0にしてから、

上下左右に+1をして、隣接するマスが島かどうかをもう一度DFS関数を呼び出すことでチェックする。

1から0に変更するのは、同じ島を2回以上重複して探索することを防ぐため。

上下左右に探索場所を変えながら島であるかをチェックするので、同じマスに戻ってくることがある。

 

 

個人的にはこちらの方がすっきり読めるものの、計算量では解答2の方が良い。

 

 

 

解答2:Python, DFS

 

解答1とほぼ同じ。

DFS関数の中で変わっているのは、1から0に変えるタイミングと、

上下左右に探索を広げるかの判断を4つのif文に分けているところ。

 

 

 

メモ・参考・感想

■類題

695. Max Area of Island

733. Flood Fill

 

 

 

前:986. Interval List Intersections

次:40. Combination Sum II

LeetCode 解答・解説記事一覧

コメント