paizaラーニング グリッド版ダイクストラ問題セット:問題1 幅優先探索 – 迷路(Python解答例)

スポンサーリンク

はじめに

前回は導入ということで単純な問題だったが、次は一歩踏み込んだロジックが必要になる。次に探索するものと、探索が終わったものを管理する仕組みを作る。自分はpandasを使ったやり方しか思いつかなかったが、他にも良い方法があると思う。pandasの基本については解説を省略する。

ちなみにpaizaの解説記事ではコストを管理しない書き方になっているのだが、この書き方は本当に正しいのだろうか。私はJavaが分からないので正確なことは不明だが、[2,0]の地点を探索した時のコストがどうなっているのか良く分からない。ゴール到達時に足さなければいけない1を[2,0]地点で足してしまっているように見える。

もう少し複雑な形になっても想定通り動くのだろうか。自分が最初に解いた時は分からなかったのだが、今となっては違和感を覚える。だが、Javaが分からないので何とも言えない。

前の問題の解説記事
次の問題の解説記事
paizaの問題へのリンク(グリッド版ダイクストラ問題セット)

(プログラミング初心者による)解説

基本部分

基本部分は前回とほぼ同じ。通過する地点の数を数えるので、costは初期値が1になる([0,0]をカウントするため)。

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
R, U, L, D = 0, 1, 2, 3

H, W = map(int, input().split())
graph = []
for _ in range(H):
    graph.append([int(_) for _ in input().split()])

sx, sy = 0, 0
gx, gy = W - 1, H - 1

moves = [R, U, L, D]
cost = 1

pandasのDataFrameに入れる

次に探索する地点のリストをnext_listとし、探索が終わったものをclosed_listに入れる。この時、x,y座標の他に、その地点に到達するまでの累計コストを管理するcostも追加する。このリストをpandasのDataFrameに入れる。pandasを使うのはこの先で使う部分一致とソートが便利という理由なので、他に何か方法が分かる人はpandas以外で対応できると思う。

import pandas as pd

next_list = [[sx, sy, 1]]  # x,y,cost
closed_list = []
df_n = pd.DataFrame(next_list, columns=['x', 'y', 'cost'])
df_c = pd.DataFrame(closed_list, columns=['x', 'y', 'cost'])

whileループ

ここから先はwhileとforを組み合わせたループを使う。ここではflag=1の時にwhileを抜ける。df_n.iloc[0]で次に探索すべき地点の一番上を取ってきてtmpに入れる。取った分はdropで削除し、tmpの中身はx,y,cに入れる。

if len の行では、すでに探索した地点がdf_cに存在するか否かを判定している。forループの一番下ではコストをc + 1で1増加したものをdf_nに追加する。

forループを抜けたところでdf_cに今調べた地点を入れる。df_nをsort_valuesでcostの小さい順に並べ替えて、reset_indexでインデックスを振り直す。インデックスを振り直さないと、次のループでindex=[0]を取得するのが上手く行かない。

flag = 0
while flag == 0:
    breakpoint()
    tmp = df_n.iloc[0]
    df_n.drop(index=[0], inplace=True)
    x, y, c = tmp
    for i in moves:
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= W or ny < 0 or ny >= H:
            continue
        if g[ny][nx] == 1:
            continue
        if len(df_c[(df_c['x'] == nx) & (df_c['y'] == ny)]) > 0:
            continue
        if nx == gx and ny == gy:
            print(c + 1)
            flag = 1
            break
        df_n = df_n.append({'x': nx, 'y': ny, 'cost': c + 1}, ignore_index=True)
    df_c = df_c.append({'x': x, 'y': y, 'cost': c}, ignore_index=True)
    df_n.sort_values('cost', inplace=True)
    df_n.reset_index(inplace=True, drop=True)

コード全体

import pandas as pd

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
R, U, L, D = 0, 1, 2, 3

H, W = map(int, input().split())
g = []
for _ in range(H):
    g.append([int(_) for _ in input().split()])

sx, sy = 0, 0
gx, gy = W - 1, H - 1

moves = [R, U, L, D]
cost = 1

next_list = [[sx, sy, 1]]  # x,y,cost
closed_list = []
df_n = pd.DataFrame(next_list, columns=['x', 'y', 'cost'])
df_c = pd.DataFrame(closed_list, columns=['x', 'y', 'cost'])

flag = 0
while flag == 0:
    breakpoint()
    tmp = df_n.iloc[0]
    df_n.drop(index=[0], inplace=True)
    x, y, c = tmp
    for i in moves:
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= W or ny < 0 or ny >= H:
            continue
        if g[ny][nx] == 1:
            continue
        if len(df_c[(df_c['x'] == nx) & (df_c['y'] == ny)]) > 0:
            continue
        if nx == gx and ny == gy:
            print(c + 1)
            flag = 1
            break
        df_n = df_n.append({'x': nx, 'y': ny, 'cost': c + 1}, ignore_index=True)
    df_c = df_c.append({'x': x, 'y': y, 'cost': c}, ignore_index=True)
    df_n.sort_values('cost', inplace=True)
    df_n.reset_index(inplace=True, drop=True)

「pandasでpaiza問題」記事一覧へのリンク

コメント

当ブログのコンテンツが気に入ったら広告ブロックの解除(ホワイトリスト化)をご検討下さい。

Please disable your adblocker or whitelist this site!

タイトルとURLをコピーしました