leetcode number of island

はい

最初に考えたのは、

順になめていって、１があったらそれは島なのでdfsで島全体を探索し

終わったら続ける

というようなものです

味噌は、終わったポイントは１以外でうわがきしてしまえば処理が楽ということです

最初の解

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        num = 0
        #self.print(S)
        for i, row in enumerate(S):
            for j, s in enumerate(row):
                #print(s, S[i][j])
                if s == '1':
                    num += 1
                    ##print('-'*8)
                    self.explore(S, i, j)
                    #sself.print(S)
                else:
                    pass

        return num

    def print(self, S):
        for row in S:
            print(row)

    def get(self, S, i, j):
        try:
            if i < 0 or j < 0: return None
            else: return S[i][j]
        except:
            return None

    def explore(self, S, i, j):
        stack = []
        stack.append((i, j))
        while len(stack) > 0:
            i, j = stack.pop()
            for ni, nj in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
                if self.get(S, ni, nj) == '1':
                    stack.append((ni, nj))
            S[i][j] = '0' # overwrite

そのあと別の回答を見てマネをして書き直してみたのが以下

とてもスッキリかけていますが、実行速度は全く同じです。

むしろ最初の解はスタックを使っている分、再帰呼び出しでスタックりょういき

を使ったり、再帰呼び出し制限とか気にしなくて良い分良かったりする面もありますね。

class Solution2:
    def numIslands(self, grid: List[List[str]]) -> int:
        def sinkIsland(grid, r, c):
            if (r < 0 or r >= len(grid) or
                c < 0 or c >= len(grid[0]) or
                grid[r][c] != '1'
            ):
                return
            else: # means grid[r][c] is 1
                grid[r][c] = '#'
                sinkIsland(grid, r-1, c)
                sinkIsland(grid, r+1, c)
                sinkIsland(grid, r, c-1)
                sinkIsland(grid, r, c+1)

        counter = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    counter += 1
                    sinkIsland(grid, i, j)
        return counter

良い点はやっぱり断然スッキリかけているところですね。

実行分析は

舐めるのでn*m, でdfsで最大(n*m)なのですからO(2(n*m))ですが最悪でのケースなので

time complexitはと聞かれれば素直に

time => O(n*m)

space => O(1)

です。