こんにちは
今回の学びは
・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で解けそうという定番のあわせ技
以上です