[伯俊]1697-かくれんぼ(Python)

質問リンク

質問する

秀斌は弟と隠れん坊をしている.秀彬は現在点N(0≦N≦100000)、弟は点K(0≦K≦100000)にいる.スビンは歩いたり瞬時に移動したりすることができます秀彬の位置がXであれば、1秒後にX-1またはX+1に移動します.瞬間移動なら1秒後に2*Xの位置に移動します.
もし秀彬と弟の位置があれば、秀彬が弟を探す最も速い時間は数秒後であることを求めるプログラムを書きます.

アルゴリズム#アルゴリズム#

グラフィック理論

グラフィックナビゲーション

幅優先ナビゲーション(bfs)

入力

一行目はスビンのポジションNと弟のポジションKNとKは整数です.

しゅつりょく

秀彬が弟を探している一番速い時間を印刷します.

入力例

5 17

出力例

4

I/O例説明

秀斌は5→10→9→18→17の順に歩いて、4秒で弟を見つけることができます.

に答える

この問題は幅優先探索(BFS)アルゴリズムを採用した.
AからBへの最短経路を求める問題ではBFSが適切であると考えられる.
DFS(深度優先ナビゲーション)

BFS(幅優先ナビゲーション)

画像ソース-https://developer-mac.tistory.com/64
秀彬は1秒以内に現在の位置+1 or-1,or*2を移動することができる.
したがって、開始位置が5であれば
1秒で行ける場所-4.6.10
2秒以内に行ける場所-3、5、8、7、12、9、11、20
3秒以内に行ける場所-2,16、・・・、18、・・・
4秒以内に行ける場所-1、・・・、17、・・・
1秒あたり到達可能な4、6、10の情報をリストに記録します.
ex) [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1]
4、6、10からそれぞれ行ける場所を調べます.
2秒で行ける場所なので、リストに2と表示されます.
このとき、すでにその位置にゼロ以外の数字があれば、通過します.

コード#コード#

from collections import deque


def bfs(MAX, start, target):

    dist = [0] * (MAX + 1)
    q = deque()
    q.append(start)
    
    while q:
        x = q.popleft()
        if x == target:
            return dist[x]

        for i in (x - 1, x + 1, x * 2):
            if 0 <= i <= MAX and not dist[i]:
                dist[i] = dist[x] + 1
                q.append(i)


MAX = 100000
N, K = map(int, input().split())
print(bfs(MAX, N, K))

コードの説明

上記の情報を含むdist配列を宣言し,与えられた最大値(10万)に基づいて0に初期化する.

pythonライブラリdequeを宣言します.一方の方向にしか入力できず、他方の方向にしか出力できない通常のキューとは異なり、dequeは双方向に入力出力できるデータ構造である.初期値は開始値(5)とします.

無限複文を回し、dequeの一番左の数字をxに代入します.(popleft)

x−1,x+1,x*2の3つを調べた後,得られた値が範囲外であり,distに記録されていない場合はdistに記録しdequeに入れる.

Dequeの値がターゲット値と一致する場合、distから値を取り出して返します.