Pythonで解いたLeetCodeの問題をSwiftで解いてみよう「200. Number of Islands」

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

# 問題
[200. Number of Islands](https://leetcode.com/problems/number-of-islands/)

1（陸）と0（水）の地図を表すm×nの2次元2進格子が与えられたとき、島の数を返しなさいという問題。
前回から進歩して**Medium**の問題に進出しました。めでたい。

問題文の中に
>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.

とあるように、

```Python
[
["0","1","0"],
["1","1","1"],
["0","1","0"]
]
```
であれば島の数は1つとなり、

```Python
[
["0","1","0"],
["1","0","1"],
["0","1","0"]
]
```
となれば島の数は4つとなる。

# Pythonで実装

グラフなんだからDFSとBFSで書いてみる。
UnionFindは書きません。

まずDFS。

```Python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(row, col):
            if rows > row >= 0 and cols > col >= 0 and grid[row][col] == "1":
                grid[row][col] = "0"
                dfs(row + 1, col)
                dfs(row - 1, col)
                dfs(row, col + 1)
                dfs(row, col - 1)

        if not grid:
            return 0

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

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    dfs(i, j)
                    number_of_islands += 1

        return number_of_islands
# Runtime Details 267ms Beats 88.38%of users with Python3
# Memory Details 18.92MB Beats 56.31%of users with Python3
```

パッと聞かれた時に答えやすい。
計算量と空間計算量ともにO(N*M)で二次元配列の長さに依存する。



今度はBFS。

```Python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def bfs(row, col):
            
            queue = collections.deque()
            queue.append((row,col))

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

        if not grid:
            return 0

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

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    bfs(i, j)
                    number_of_islands += 1

        return number_of_islands
# Runtime Details 273ms Beats 81.23%of users with Python3
# Memory Details 18.55MB Beats 95.63%of users with Python3
```

こちらも計算量と空間計算量ともにO(N*M)で二次元配列の長さに依存する。


# Swiftで実装

上記と同様の内容をSwiftで書き直してみる。

```Swift
class Solution {
    func numIslands(_ grid: [[Character]]) -> Int {
        var grid = grid

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

        if grid.isEmpty{
            return 0
        }

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

        for i in 0..<rows{
            for j in 0..<cols{
                if grid[i][j] == "1"{
                    dfs(row:i,col:j)
                    numberOfIslands += 1
                }
            }
        }

        return numberOfIslands
    }
}
// Runtime Details 9ms Beats 83.54%of users with Swift
// Memory Details 14.73MB Beats 61.10%of users with Swift
```

最初Pythonの時の書き方の
```Python
if rows > row >= 0 and cols > col >= 0 and grid[row][col] == "1":
```

を真似て書いたら

```terminal
adjacent operators are in non-associative precedence group 'ComparisonPrecedence' in solution.swift
```

と怒られたくらいで、それ以外はあっさり通った。


BFSはというと、

```Swift
class Solution {
    func numIslands(_ grid: [[Character]]) -> Int {
        var grid = grid

        func bfs(row:Int,col:Int){
            
            var queue = [(row, col)]

            while !queue.isEmpty{
                let (qr,qc) = queue.removeFirst()
                if 0 <= qr && qr < rows && 0 <= qc && qc < cols && grid[qr][qc] == "1" {
                    grid[qr][qc] = "0"
                    queue.append((qr+1,qc))
                    queue.append((qr-1,qc))
                    queue.append((qr,qc+1))
                    queue.append((qr,qc-1))
                    }
            }
        }

        if grid.isEmpty{
            return 0
        }

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

        for i in 0..<rows{
            for j in 0..<cols{
                if grid[i][j] == "1"{
                    bfs(row:i,col:j)
                    numberOfIslands += 1
                }
            }
        }

        return numberOfIslands
    }
}

// Runtime Details 14ms Beats 10.22% of users with Swift 
// Memory Details 14.90MB Beats 38.65% of users with Swift
```

これも解き方さえ分かっていれば分岐以外に特に気をつけることはなかった。

少し冗長になりがちな部分があるからめんどくさくなる時が結構ある。
Pythonだったら適当に書いても動くというのが正しいかもしれない。
そういう意味で言うと、関数アノテーションなどがあるとはいえ、初心者がいきなりPythonを触るのは一長一短感があると思った。

次もグラフを解く予定。


# 追記(11/4)


@nak435 さんにSwiftでの分岐の綺麗な書き方を教えていただけたので修正しておきました。
Swiftビギナーの私にはとてもありがたいです。

以下DFSの書き換え。

```diff_swift
class Solution {
    func numIslands(_ grid: [[Character]]) -> Int {
        var grid = grid

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

                grid[row][col] = "0"
                dfs(row: row + 1, col: col)
                dfs(row: row - 1, col: col)
                dfs(row: row, col: col + 1)
                dfs(row: row, col: col - 1)
            }
        }

        if grid.isEmpty{
            return 0
        }

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

        for i in 0..<rows{
            for j in 0..<cols{
                if grid[i][j] == "1"{
                    dfs(row:i,col:j)
                    numberOfIslands += 1
                }
            }
        }

        return numberOfIslands
    }
}
// Runtime Details 9ms Beats 83.54%of users with Swift
// Memory Details 14.73MB Beats 61.10%of users with Swift

```

以下BFSの書き換え。

```diff_swift
class Solution {
    func numIslands(_ grid: [[Character]]) -> Int {
        var grid = grid

        func bfs(row:Int,col:Int){
            
            var queue = [(row, col)]

            while !queue.isEmpty{
                let (qr,qc) = queue.removeFirst()
-                if 0 <= qr && qr < rows && 0 <= qc && qc < cols && grid[qr][qc] == "1" {
+                if 0 ..< rows ~= qr && 0 ..< cols ~= qc && grid[qr][qc] == "1" {
                    grid[qr][qc] = "0"
                    queue.append((qr+1,qc))
                    queue.append((qr-1,qc))
                    queue.append((qr,qc+1))
                    queue.append((qr,qc-1))
                    }
            }
        }

        if grid.isEmpty{
            return 0
        }

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

        for i in 0..<rows{
            for j in 0..<cols{
                if grid[i][j] == "1"{
                    bfs(row:i,col:j)
                    numberOfIslands += 1
                }
            }
        }

        return numberOfIslands
    }
}

// Runtime Details 14ms Beats 10.22% of users with Swift 
// Memory Details 14.90MB Beats 38.65% of users with Swift

```

ありがとうございます！！