DFS（深さ優先探索）が難しすぎるので、前段階のプログラムを作成した

Depth-First-Searchの記事を公開しようとしたが、再帰処理の理解が出来なかった。

そのため、最小単位のサンプルコードを作成した。

一歩一歩、歩いて行こう。

できることを積み上げていくと、複雑なプログラムが作れるようになる。

ソースコード

python/dfs.py at 099d4188f9d6cdb4df04927893a3c4c75dd685ff · ki-hi-ro/python

grid = [
    [1, 5],
    [0, 9]
]

H, W = len(grid), len(grid[0])
directions = [(1,0), (-1,0), (0,1), (0,-1)]

max_score = 0
best_path = []

print("=== 全パターン ===")
for y in range(H):
    for x in range(W):
        start = grid[y][x]
        for dy, dx in directions:
            ny, nx = y + dy, x + dx
            if 0 <= ny < H and 0 <= nx < W:
                score = start + grid[ny][nx]
                path = [(y, x), (ny, nx)]
                print(f"{path} → 合計={score}")
                if score > max_score:
                    max_score = score
                    best_path = path

print("\n🏆 最大合計:", max_score)
print("通った座標:", best_path)

出力結果

=== 全パターン ===
[(0, 0), (1, 0)] → 合計=1
[(0, 0), (0, 1)] → 合計=6
[(0, 1), (1, 1)] → 合計=14
[(0, 1), (0, 0)] → 合計=6
[(1, 0), (0, 0)] → 合計=1
[(1, 0), (1, 1)] → 合計=9
[(1, 1), (0, 1)] → 合計=14
[(1, 1), (1, 0)] → 合計=9

🏆 最大合計: 14
通った座標: [(0, 1), (1, 1)]

解説

まずは、定義部分。

grid = [
    [1, 5],
    [0, 9]
]

H, W = len(grid), len(grid[0])
directions = [(1,0), (-1,0), (0,1), (0,-1)]

max_score = 0
best_path = []

2×2のグリッドと、高さと幅、上下左右の移動方向、最大スコア、最大スコアを出した時の移動経路を定義している。

続いて、出力フェーズ。

print("=== 全パターン ===")
for y in range(H):
    for x in range(W):
        start = grid[y][x]
        for dy, dx in directions:
            ny, nx = y + dy, x + dx
            if 0 <= ny < H and 0 <= nx < W:
                score = start + grid[ny][nx]
                path = [(y, x), (ny, nx)]
                print(f"{path} → 合計={score}")
                if score > max_score:
                    max_score = score
                    best_path = path

print("\n🏆 最大合計:", max_score)
print("通った座標:", best_path)

=== 全パターン ===と出力した後に、for文に突入する。

print("=== 全パターン ===")
for y in range(H):
    for x in range(W):

最初の値をstartに格納する。

   start = grid[y][x]

4方向について、スコアを調べていく。

        for dy, dx in directions:

ny, nxは、進んだ先の座標になる。

            ny, nx = y + dy, x + dx

ny, nxがグリッドの範囲内であれば、

            if 0 <= ny < H and 0 <= nx < W:

scoreに、最初の値と進んだ先の値を合計した値を代入する。

                score = start + grid[ny][nx]

pathに、最初の座標と進んだ先の座標を格納したリストを代入する。

                path = [(y, x), (ny, nx)]

経路とスコアを表示する。

                print(f"{path} → 合計={score}")

scoreがmax_scoreよりも大きければ、max_scoreとbest_pathを更新する。

                  if score > max_score:
                    max_score = score
                    best_path = path

print("\n🏆 最大合計:", max_score)
print("通った座標:", best_path)

forループを抜けた後は、max_scoreとbest_pathを出力する。

print("\n🏆 最大合計:", max_score)
print("通った座標:", best_path)