paizaラーニング グリッド版ダイクストラ問題セット:問題2 ダイクストラ法 – 最短経路のコスト(Python解答例)

スポンサーリンク

はじめに

コストの計算が違うだけで、前の問題と同じような解き方になっている。ここではコストが一番小さい地点から最初に探索するようにする方法がpandasのsort_valueを使う方法なのだが、恐らく他にもっと高速な方法があると思う(現時点で筆者には分からない)。

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

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

問題1との相違点

コストの計算では最初の地点を0にしておく。また、累積コストをncで計算する。

next_list = [[sx, sy, 0]]  # x,y,cost

nc = c + g[ny][nx]

コード全体

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]

next_list = [[sx, sy, 0]]  # 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
        nc = c + g[ny][nx]
        if len(df_c[(df_c['x'] == nx) & (df_c['y'] == ny)
                    & (df_c['cost'] <= nc)]) > 0:
            continue
        if len(df_n[(df_n['x'] == nx) & (df_n['y'] == ny)
                    & (df_n['cost'] <= nc)]) > 0:
            continue
        if nx == gx and ny == gy:
            print(nc)
            flag = 1
            break
        df_n = df_n.append({'x': nx, 'y': ny, 'cost': nc}, 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をコピーしました