【LeetCode】695. Max Area of Island 解答・解説【Python】

はじめに
問題
1. 原文
2. 内容
解答
1. 解答1：Python,DFS
補足・参考・感想

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

問題

原文

You are given an m x n binary matrix grid. An island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] Output: 6 Explanation: The answer is not 11, because the island must be connected 4-directionally.

1
2
3

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]] Output: 0

1
2

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

m == grid.length

n == grid[i].length

1 <= m, n <= 50

grid[i][j] is either 0 or 1.

内容

m×nの二次元配列gridが与えられます。島は1で表され、横方向か縦方向でつながっています。

gridの外側は水でおおわれているものとします。島の面積は1です。

島の最大サイズを返してください。島が泣ければ0を返してください。

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

解答

解答1：Python,DFS

class Solution:    
    #深さ優先探索で、連続する島の最大面積を求める
    def dfs(self, grid, row, column):
　　　　　#gridの範囲外か、マスの値が1以外の場合は0を返す
        if row<0 or column<0 or row>=len(grid) or column>=len(grid[0]) or grid[row][column]!=1:
            return 0
        else:
            #島を発見する度に大きさを1にする。　※初期化しないと前回発見した島のサイズから始めてしまう
            max_area = 1
            #訪問済みの島は1以外にする。　※1のままだと同じ島をぐるぐる永遠に回って数え続ける
            grid[row][column] = "#"
            #上下左右の隣接エリアが島なら+1する。これを隣接エリアが島である限り続ける
            max_area += self.dfs(grid,row+1,column)
            max_area += self.dfs(grid,row-1,column)
            max_area += self.dfs(grid,row,column+1)
            max_area += self.dfs(grid,row,column-1)

            return max_area    
    
    #解答
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        #最大エリア数を0で初期化
        max_area = 0
        #gridの行数
        for row in range(len(grid)):
            #gridの列数
            for column in range(len(grid[0])):
                #あるマスの値が1、つまり島である場合
                if grid[row][column]==1:
                    #max_areaを更新するために、現在のmax_areaか、dfs関数実行結果の大きい方をmax_areaに代入
                    max_area = max(max_area, self.dfs(grid,row,column))
        #最大エリア数を返す
        return max_area

class Solution:

#深さ優先探索で、連続する島の最大面積を求める

def dfs(self, grid, row, column):

　　　　　#gridの範囲外か、マスの値が1以外の場合は0を返す

if row<0 or column<0 or row>=len(grid) or column>=len(grid[0]) or grid[row][column]!=1:

return 0

else:

#島を発見する度に大きさを1にする。　※初期化しないと前回発見した島のサイズから始めてしまう

max_area = 1

#訪問済みの島は1以外にする。　※1のままだと同じ島をぐるぐる永遠に回って数え続ける

grid[row][column] = "#"

#上下左右の隣接エリアが島なら+1する。これを隣接エリアが島である限り続ける

max_area += self.dfs(grid,row+1,column)

max_area += self.dfs(grid,row-1,column)

max_area += self.dfs(grid,row,column+1)

max_area += self.dfs(grid,row,column-1)

return max_area

#解答

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

#最大エリア数を0で初期化

max_area = 0

#gridの行数

for row in range(len(grid)):

#gridの列数

for column in range(len(grid[0])):

#あるマスの値が1、つまり島である場合

if grid[row][column]==1:

#max_areaを更新するために、現在のmax_areaか、dfs関数実行結果の大きい方をmax_areaに代入

max_area = max(max_area, self.dfs(grid,row,column))

#最大エリア数を返す

return max_area

最初に深さ優先探索で島の最大面積を調べる関数dfsを作り、

2つ目の関数でこの問題の解答を返す関数maxAreaOfIslandを作っています。

関数maxAreaOfIslandでは、for文を二つ使って2重ループで二次元配列gridを全探索しています。

全要素を順番に調べ、その値が1だった場合、島の最大面積を調べる処理に入ります。

島の最大面積を調べるには、現在の最大面積と、関数dfsの実行結果を比べて、

その値の大きい方を最大面積とする方法をとっています。

最後まで探索が終われたらmax_areaの値を返して終了します。

関数dfsでは、探索対象のgridと、呼び出された時点での行番号と列番号を引数に取ります。

まず、現在探索中の要素が島であるかを判定するため、以下の2つの条件に当てはまるかを調べます。

・row<0 , columns<0, row>len(grid) , column> len(grid[0])

これは二次元配列gridの外側であることを意味します。

・grid[row][column]!=1

これは島であることをあらわす1以外の値を持っていることを意味します。

上記のどれかの条件に当てはまればgrid内の島ではないので、0を返します。

次に、現在探索中の島の面積である1を保持します。

この値を後で呼び出し元に返すことで、島の最大面積に1が加えられます。

次に、現在探索中の島の値を1とは別の値に変更します。　※今回は”#”

上下左右に隣接する島がある限り関数dfsの処理が繰り返されるので、

値を変更しておくことで探索対象から外れるようにします。

最後に、上下左右に隣接する島を対象に再帰的にdfs関数を呼び出します。

これにより、隣接するマスが島であった分だけ最大面積に1が加えられます。

補足・参考・感想

■類題

200. Number of Islands

733. Flood Fill

前：733. Flood Fill

次：617. Merge Two Binary Trees

LeetCode 解答・解説記事一覧