Pythonで解いたLeetCodeの問題をSwiftで解いてみよう「695. Max Area of Island」

# 概要
[ゼロから始めるLeetCode](https://qiita.com/KueharX/items/6ee2502c3b620c795b70)の時に解いた問題とかをSwiftで書いてみることにした。
シリーズ化するかは不明。

# 問題
[695. Max Area of Island](https://leetcode.com/problems/max-area-of-island/)

1（陸）と0（水）の地図を表すm×nの2次元2進格子が与えられたとき、一番大きい島の面積を返しなさいという問題。
前回に引き続き**Medium**の問題です。


```Python
[
["0","1","0"],
["1","1","1"],
["0","1","0"]
]
```
であれば島の面積は5となり、

```Python
[
["0","1","0"],
["1","0","1"],
["0","1","0"]
]
```
となれば島の面積は1となる。

# Pythonで実装

グラフなんだからDFSとBFSで書いてみる。

まずDFS。

```Python
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        rows,cols = len(grid),len(grid[0])
        maxArea = 0

        def dfs(row,col):
            if 0 <= col < cols and 0 <= row < rows and grid[row][col] == 1:
                grid[row][col] = 0
                return 1 + dfs(row+1,col) + dfs(row-1,col) + dfs(row,col+1) + dfs(row,col-1)
            return 0


        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    tempCount = dfs(i,j)
                    maxArea = max(maxArea,tempCount)
        return maxArea
# Runtime Details 119ms Beats 82.74%of users with Python3
# Memory Details 18.92MB Beats 63.58%of users with Python3
```

前回同様、再帰処理が分かっていれば想像しやすい。
ただ、通った後に思ったけど、これだと上から下に読んだ時の視認性が悪いと感じたので書き直した。

```python
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        self.grid = grid
        self.rows, self.cols = len(grid), len(grid[0])
        self.maxArea = 0

        for i in range(self.rows):
            for j in range(self.cols):
                if self.grid[i][j] == 1:
                    tempCount = self.dfs(i, j)
                    self.maxArea = max(self.maxArea, tempCount)

        return self.maxArea

    def dfs(self, row, col):
        if 0 <= col < self.cols and 0 <= row < self.rows and self.grid[row][col] == 1:
            self.grid[row][col] = 0
            return 1 + self.dfs(row+1, col) + self.dfs(row-1, col) + self.dfs(row, col+1) + self.dfs(row, col-1)
        return 0
# Runtime Details 119ms Beats 82.74%of users with Python3
# Memory Details 18.92MB Beats 63.58%of users with Python3
```

両方の解法をいきなり見せられた場合、こちらの方が読みやすいと思ったのでこちらで通すことにする。
計算量と空間計算量ともにO(N*M)で二次元配列の長さに依存する。


今度はBFS。今度は関数直下に書くパターンのみ。

```Python
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        rows,cols = len(grid),len(grid[0])
        maxArea = 0

        def bfs(row,col):
            queue = collections.deque()
            queue.append((row,col))
            areaCounter = 0
            while queue:
                qr,qc = queue.popleft()

                if 0 <= qr < rows and 0 <= qc < cols and grid[qr][qc] == 1:
                    grid[qr][qc] = 0
                    areaCounter += 1
                    queue.append((qr+1,qc))
                    queue.append((qr-1,qc))
                    queue.append((qr,qc+1))
                    queue.append((qr,qc-1))
            return areaCounter



        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    tempCount = bfs(i,j)
                    maxArea = max(maxArea,tempCount)
        return maxArea
# Runtime　Details　113ms　Beats 93.33%of users with Python3
# Memory Details 16.26MB Beats 99.49%of users with Python3
```

最初の回答と計算量も空間計算量も変わらないのになんかいい数値が出た。
こちらも計算量と空間計算量ともにO(N*M)で二次元配列の長さに依存する。


# Swiftで実装

上記と同様の内容をSwiftで書き直してみる。
視認性が悪くて修正する前。

```Swift
class Solution {
    func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
        if grid.isEmpty{
            return 0
        }

        var rows:Int = grid.count
        var cols:Int = grid[0].count
        var grid = grid
        var maxArea:Int = 0

        func dfs(row:Int,col:Int) -> Int{
            
            if 0 ..< rows ~= row && 0 ..< cols ~= col && grid[row][col] == 1 {
                    grid[row][col] = 0
                    return 1 + dfs(row:row+1,col:col) + dfs(row:row-1,col:col) + dfs(row:row,col:col+1) + dfs(row:row,col:col-1)
            }
            return 0
        }

        for i in 0..<rows{
            for j in 0..<cols{
                if grid[i][j] == 1{
                    let tempCount = dfs(row:i,col:j)
                    maxArea = max(maxArea,tempCount)
                }
            }
        }
        return maxArea
    }
}
// Runtime Details 57ms Beats 70.43%of users with Swift
// Memory Details 14.32MB Beats 40.32%of users with Swift
```

修正後

```swift
class Solution {
    var rows = 0
    var cols = 0
    var grid = [[Int]]()
    
    func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
        if grid.isEmpty {
            return 0
        }

        self.rows = grid.count
        self.cols = grid[0].count
        self.grid = grid
        var maxArea = 0

        for i in 0..<self.rows {
            for j in 0..<self.cols {
                if self.grid[i][j] == 1 {
                    let tempCount = dfs(row: i, col: j)
                    maxArea = max(maxArea, tempCount)
                }
            }
        }
        return maxArea
    }
    
    func dfs(row: Int, col: Int) -> Int {
        if 0 ..< self.rows ~= row && 0 ..< self.cols ~= col && self.grid[row][col] == 1 {
            self.grid[row][col] = 0
            return 1 + dfs(row: row + 1, col: col) + dfs(row: row - 1, col: col) + dfs(row: row, col: col + 1) + dfs(row: row, col: col - 1)
        }
        return 0
    }
}
// Runtime Details 57ms Beats 70.43%of users with Swift
// Memory Details 14.32MB Beats 40.32%of users with Swift
```

いずれもそこまで気をつけることはなく、単純に書き直してみました！って感じの流れだった。
強いて書くなら前回の記事でコメント頂いたif分岐の条件をSwiftっぽく書くことを意識したくらい。

BFSはというと、

```Swift
class Solution {
    func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
        if grid.isEmpty{
            return 0
        }

        var rows:Int = grid.count
        var cols:Int = grid[0].count
        var grid = grid
        var maxArea:Int = 0

        func bfs(row:Int,col:Int) -> Int{
            
            var queue = [(row,col)]
            var areaCount = 0
            while !queue.isEmpty{
                let (qr,qc) = queue.removeFirst()
                if 0 ..< rows ~= qr && 0 ..< cols ~= qc && grid[qr][qc] == 1 {
                    grid[qr][qc] = 0
                    areaCount += 1
                    queue.append((qr+1,qc))
                    queue.append((qr-1,qc))
                    queue.append((qr,qc+1))
                    queue.append((qr,qc-1))
                    }
            }
            return areaCount
        }

        for i in 0..<rows{
            for j in 0..<cols{
                if grid[i][j] == 1{
                    let tempCount = bfs(row:i,col:j)
                    maxArea = max(maxArea,tempCount)
                }
            }
        }
        return maxArea
    }
}

// Runtime Details 61ms Beats 40.32%of users with Swift
// Memory Details 13.94MB Beats 90.86%of users with Swift
```

こちらも前回コメントでもらった条件で分岐を書くくらいに気をつけたことは他になかった。
グラフだって分かったらある程度型にはめる方法が大事で、その場でのひらめきとかよりも定石を知っているかのような気がしてきたので、もしかしたら基礎の部分が徐々に固まってきたのかもしれない。

Swiftの知識がまだまだ足りないので色んな問題(主に難易度Medium以上)を解いて練習していく予定。