1. 目的

初中級者が解くべき過去問精選 100 問をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。

本記事は「024 - 027 深さ優先探索」です。

2. 総括

下記の記事では簡単に書いてますが、もともとBFSとDFSを理解するためにかなり時間がかかりました。
BFSとDFSの基本形をおさえるまでに、最初は解説を読んでもまったくわからず、理解するまでに1週間くらい（1日10時間以上悩むこともあった）かかっています。

理解するために行ったこととしては、解説記事を読むのは当然ですが、ACで通っているコードをデバックしてみて、一行ずつ、どのようにデータが動いているかを確認するということを理解できるまでやりました。
再帰については、実際にノートにすべての再帰計算を書き出したりもしました。

すると、ある時を境に、頭の中でBFSとDFSのデータ構造ができあがって、ノートに何も書かなくても、頭の中でBFS、DFS的にデータを動かせるようになっていました。
おそらくこの瞬間が訪れるのは個人差があるとは思いますが、一定量の思考（試行？）をしないと訪れないのでは、と思います。

なお、デバックはVS codeのデバッカーを使っています。便利です。こんな感じ。

3. 本編

024 - 027 深さ優先探索

024. ALDS_11_B - 深さ優先探索

回答


N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N):
    i, num, *nodes = map(int, input().split())
    graph[i] = nodes # 有向グラフ

go_time = [0] * (N+1)
back_time = [0] * (N+1)

def dfs(node, t):
    # 行きの記録
    t += 1
    go_time[node] = t
    for next_node in graph[node]:
        if go_time[next_node] == 0:
            t = dfs(next_node, t)
    # 帰りの記録
    t += 1
    back_time[node] = t
    return t

t = 0
for node in range(1, N+1): # すべての点からスタートを試す
    if go_time[node] == 0:
        t = dfs(node, t)
    print(node, go_time[node], back_time[node])

まず、データの受け取りがめんどくさいです。
グラフ情報の受け取り方ですが、長さが可変の個所はi, num, *nodes = map(int, input().split())のように、一番最後の*nodesに*を付けることでnodesに残り部分を全部渡すことができます。参考-> Pythonでタプルやリストをアンパック（複数の変数に展開して代入）

こちら提出してみるとわかりますが、1からスタートしてもたどり着けない箇所が存在する可能性があるので（これが問題文のどこで読み取れるかわからない・・・）、すべての点をスタートの候補として試す必要があります。

今回書いた再帰によるdfsも、deque(pythonの場合)によるdfsもまずは基本の型を覚える必要があり、基本の型の説明は僕にはなかなか難しいので省略します。
とりあえず、この基本形を覚える、で最初は進めていきます。

025. AOJ 1160 - 島はいくつある？

回答


from collections import deque

def main(w, h, MAP, visited):
    count = 0
    # すべての点からスタートを試す
    for start_y in range(h):
        for start_x in range(w):
            if MAP[start_y][start_x] == 0: # 海の場合は飛ばす
                continue
            if visited[start_y][start_x] != -1: # 探索済みは飛ばす
                continue
            q = deque()
            q.append((start_y, start_x))
            visited[start_y][start_x] = 1
        
            while q:
                y, x = q.pop()

                for dy in range(-1, 2):
                    for dx in range(-1, 2):
                        moved_y = y + dy
                        moved_x = x + dx

                        if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: # 地図外への移動は飛ばす
                            continue
                        if MAP[moved_y][moved_x] == 0: # 海の場合は飛ばす
                            continue
                        if visited[moved_y][moved_x] != -1: # 探索済みは飛ばす
                            continue
                        visited[moved_y][moved_x] = 1
                        q.append((moved_y, moved_x))
            
            count += 1 # whileを抜けたら1つの島
    return count

if __name__ == "__main__":

    answer_list =[]
    while True:
        w, h = map(int, input().split())
        MAP = [list(map(int, input().split())) for _ in range(h)]
        visited = [[-1] * w for _ in range(h)]

        if w == 0 and h == 0:
            break
        
        answer = main(w, h, MAP, visited)
        answer_list.append(answer)

    for answer in answer_list:
        print(answer)

個人的には再帰よりもデック(デキュー？)によるdfsのほうが書きやすいです。
これもdfsの基本形（だと思う）なので、そのまま書くだけです。

026. AtCoder Beginner Contest 138 D - Ki

回答


from collections import deque
# -------------- [入力] --------------
N, Q = map(int, input().split()) # Nは頂点の数、Qは操作の回数
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

counts = [0] * (N+1)
for _ in range(Q):
    p, x  = map(int, input().split())
    counts[p] += x
visited = [-1] * (N+1)
# -------------- [1からスタート] --------------
q = deque()
q.append(1)
visited[1] = 1
# -------------- [DFS] --------------
while q:
    node = q.pop()

    next_nodes = graph[node]
    for next in next_nodes:
        if visited[next] != -1:
            continue
        q.append(next)
        visited[next] = 1
        counts[next] += counts[node] # 親のスコアをプラスする

print(*counts[1:])

この問題は、AtCoder Beginner Contest 176 D - Wizard in Maze　（僕の回答の記事はこちら→AtCoder ABC 176 Python (A~E)）に少し似ていると感じました。この問題のほうが簡単ですが・・・。

どこが似ているかと、この問題でいうところのcounts[next] += counts[node]この部分で、ABC 176でいうとvisited[moved_y][moved_x] = visited[y][x]ここ。

どうして似ていると思ったかというと、q.pop()で抽出してきた探索対象(①とする)から、探索対象①の次の探索対象（②とする）に移る際に、①の情報を使って②の情報をアップデートするという処理が似ているからです。

通常（？）のDFS、BFSでは、上記でいう②の情報のアップデートは、ほかのリストや単なるインクリメントであることが多いと思いますが、同じリストの情報でアップデートするという方法は、一回やっておかないとなかなか思いつくのが難しいかなと思いました。
この点さえわかれば、あとはBFSの基本形とあまりかわらないです。

027. JOI 2009 予選 4 - 薄氷渡り

回答


import sys
sys.setrecursionlimit(10**9)

# -------------- [初期値] --------------
def dfs(count, start_y, start_x, visited):
    ans = count
    for dy, dx in moves:
        moved_y = start_y + dy
        moved_x = start_x + dx
        if moved_y < 0 or n-1 < moved_y or moved_x < 0 or m-1 < moved_x:
            continue
        if grid[moved_y][moved_x] == 0:
            continue
        if visited[moved_y][moved_x] != -1:
            continue
        visited[start_y][start_x] = 1
        ans = max(ans, dfs(count+1, moved_y, moved_x, visited)) # 始点から行ける最大値をとってくる
        visited[start_y][start_x] = -1
    
    return ans


if __name__ == "__main__":
    # -------------- [入力] --------------
    m = int(input()) # 横
    n = int(input()) # 縦
    grid = [list(map(int, input().split())) for _ in range(n)] # 1: 氷、0: 氷無し
    moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 上下左右のみ
    visited = [[-1] * m for _ in range(n)]
    # -------------- [すべての点をスタート地点として試す] --------------
    answer = 0
    for start_y in range(n):
        for start_x in range(m):
            if grid[start_y][start_x] == 0:
                continue
            answer = max(answer, dfs(1, start_y, start_x, visited))

    print(answer)

sys.setrecursionlimit(10**9) はなくても通りますが、備忘として残します。
これも基本形とやっていることは大体同じで、異なるのは


ans = max(ans, dfs(count+1, moved_y, moved_x, visited)) # 始点から行ける最大値をとってくる
visited[start_y][start_x] = -1

ここだけです。
これで、各始点からいける最長距離を返します。