[Algorithm] BaekJoon : 13549. かくれんぼ3 by Python

6336 ワード
python heapq baekjoon algorithm テキストリンク
[問題のショートカット]https://www.acmicpc.net/problem/13549

📌問題の説明


秀斌は弟と隠れん坊をしている.秀彬は現在点N(0≦N≦100000)、弟は点K(0≦K≦100000)にいる.スビンは歩いたり瞬時に移動したりすることができます秀彬の位置がXであれば、1秒後にX-1またはX+1に移動します.瞬間移動であれば、0秒後には2*Xの位置に移動します.
もし秀彬と弟の位置があれば、秀彬が弟を探す最も速い時間は数秒後であることを求めるプログラムを書きます.
入力
一行目はスビンのポジションNと弟のポジションKNとKは整数です.
しゅつりょく
秀彬が弟を探している一番速い時間を印刷します.

💡 問題を解く


HeapqのBFSを用いて問題を解決した.
一番早い時間を探すときは、瞬間移動がポイントです.(瞬間移動で0秒かかるから!)
3つの場合(x-1,x+1,x*2)には,移動時の時間と位置を計算し,優先キュー(heapq)に入れる.
この場合、優先順位は当然「時間」です.優先キュー(heapq)に(時間、位置)として入れ、時間を基準に最小のhip資料構造を作成します.
  • (時間、位置)という形で優先キューに入れられているので、瞬間移動から実行が開始される.
  • の瞬時移動に要する時間は0であるため、x*2の位置はいずれも0となる.
  • x*2の位置(=移動されていない位置)でない場合は、x+1、x-1に移動する必要があります.
    →移動時間+1で更新します.
    • ナビゲーション時に、その位置で移動距離値(int(1 e 9ではない)に更新された場合、その値が返されます.
    コードは次のとおりです.
    import sys, heapq

N, K = map(int, input().split())
check = [int(1e9)] * 100001
check[N] = 0
heap = []
heapq.heappush(heap, (0, N))

while heap:
    move, idx = heapq.heappop(heap)
    if check[K] != int(1e9):
        break
    for value in [idx*2, idx-1, idx+1]:
        if 0 <= value < 100001:
            if check[value] == int(1e9) and idx*2 == value:
                heapq.heappush(heap, (move, value))
                check[value] = move
            elif check[value] == int(1e9):
                heapq.heappush(heap, (move+1, value))
                check[value] = move+1
print(check[K])
    [React] Hooks
    Activityの起動モード