2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@KueharX(くえはる)

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

2
Last updated at Posted at 2023-11-03

概要

ゼロから始めるLeetCodeの時に解いた問題とかをSwiftで書いてみることにした。
シリーズ化するかは不明。

問題

200. 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.

とあるように、

[
["0","1","0"],
["1","1","1"],
["0","1","0"]
]

であれば島の数は1つとなり、

[
["0","1","0"],
["1","0","1"],
["0","1","0"]
]

となれば島の数は4つとなる。

Pythonで実装

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

まずDFS。

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。

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で書き直してみる。

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の時の書き方の

if rows > row >= 0 and cols > col >= 0 and grid[row][col] == "1":

を真似て書いたら

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

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

BFSはというと、

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の書き換え。

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の書き換え。

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

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

2
2
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?