いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 200 number of islands

投稿日:

こんにちは

今回の学びは

number of islandsはグラフ問題の代表作

・問題をグラフ問題に変換してdfsで解けそうという定番のあわせ技

 

問題は。。。

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

この問題はかなり有名だとおもいます。

与えられた配列をグラフと見立てて、連続する

とある条件をdfsしていく、という問に変換します

 

visitted といS(n)をもうけて、O(n)で処理できるとおもいます

とある条件とはdfsが前のノードと同値 そのノードの値が1だったら

という条件でいかきます。さらにいくつ島が合ったかの合計を返すようにしようかな、とおもう。

i, jで配列をループして、dfsにかける。返り値が1以上なら島ということに

して最後にその合計をかぞえる。にしよう。

 

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析)は O(n)  , S(n+n)

 

 

実際の実装はこちら

class Solution:
    def numIslands(self, S: List[List[str]]) -> int:
        m = len(S)
        if m == 0: return 0
        n = len(S[0])
        visit = [ [False] * n for _ in range(m) ]

        # def neighbours(i, j):
        #     directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        #     nbs = []
        #     for h, v in directions:
        #         if 0 <= i + v < n and 0 <= j + h < m:
        #             nbs.append((i+v, j+h))
        #     return nbs
        def neighbours(i, j):
            return [
                (i + a, j + b)
                for (a, b) in [(-1, 0), (1, 0), (0, -1), (0, 1)]
                if 0 <= i + a < m
                if 0 <= j + b < n
            ]

        # dfsのポイント!親にもどらないようにしないと永遠に再帰する
        def dfs_forever(i, j, sofar=0):
            ttl = sofar
            if S[i][j] == '1':
                for v, h in neighbours(i, j):
                    if not visit[v][h]:
                        ttl += dfs(v, h, sofar+1)
            #visit[i][j] == True # わぉ!、こんなミスが!!! (その後下のように変更修正) まぁ、それでも永遠再帰には変わりないw
            visit[i][j] = True #
            return ttl

        # dfsのポイント!親にもどらないようにしないと永遠に再帰する
        def dfs_still_forever(i, j, parent:tuple = None, sofar=0):
            ttl = sofar
            if S[i][j] == '1':
                for v, h in neighbours(i, j):
                    if not visit[v][h]:
                        if parent == None or parent != (i, j):
                            ttl += dfs(v, h, (i, j), sofar+1)
            visit[i][j] == True
            return ttl
        # dfsのポイント!そうじゃないんだ!visitフラッグのタイミングを冒頭にすればいいだけなんだ!
        # しかし、ほぼ正解なんだが、[[1]]などのエッジケースでとりこぼすぞ!
        def dfs_edge(i, j, sofar=0):
            visit[i][j] = True
            ttl = sofar
            if S[i][j] == '1':
                for v, h in neighbours(i, j):
                    if not visit[v][h]:
                        ttl += dfs(v, h, sofar+1)
            return ttl

        # うえのようなエッジケースをカバーした正解dfsがこちら
        # ttlに最初に+1しているのが、変更点です。おわかりいただけただろうか。
        def dfs(i, j, sofar=0):
            visit[i][j] = True
            ttl = sofar
            if S[i][j] == '1':
                ttl += 1
                for v, h in neighbours(i, j):
                    if not visit[v][h]:
                        ttl += dfs(v, h, ttl)
            return ttl

        ans = 0
        for i in range(m):
            for j in range(n):
                if not visit[i][j]:
                    if dfs(i, j) > 0:
                        ans += 1
        return ans

 

僕の中で number of islandsはグラフ問題の代表作 です。

問題をグラフ問題に変換してdfsで解けそうという定番のあわせ技

 

既にvisit済の状態をもつべきか

さっき来た親を知っているべきか、しらなくてもvisit状態がわかればいいのか。

それを踏まえ、どのタイミングでvisit状態とするのか

など

慎重に考えを重ねるポイントがあります。

また返り値も何にするかなど

総合的に、典型的なグラフ問題で考えるべきポイントが自然にあらわれる

良問でした。

 

実装後です。timespace analysis (時間とスペースの分析)は 

O(n)です

 

前にもでましたが、nighbours関数便利です。

pythonで競技プログラミングをする際のチップにも追記しました。

# def neighbours(i, j):
        #     directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        #     nbs = []
        #     for h, v in directions:
        #         if 0 <= i + v < n and 0 <= j + h < m:
        #             nbs.append((i+v, j+h))
        #     return nbs
        def neighbours(i, j):
            return [
                (i + a, j + b)
                for (a, b) in [(-1, 0), (1, 0), (0, -1), (0, 1)]
                if 0 <= i + a < m
                if 0 <= j + b < n
            ]

 

まとめ

number of islandsはグラフ問題の代表作

・問題をグラフ問題に変換してdfsで解けそうという定番のあわせ技

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.