【伯俊】【Python】13549号かくれんぼ3

💡 詰まった部分
従来の鬼ごっことは異なり,2倍移動すると重みは0となる.だから、graph[nx]=graph[x]+1部分をgraph[nx]=graph[x]に処理すれば、同じではないかと思って提出しましたが、間違っていました.
💡解答方法
エラーの原因はfor文の順序です.この問題には3つの状況がある.すなわち,for文によって3つの場合を巡回するには,その順序がこの問題において非常に重要である.
まず、私たちが探しているのは最高価格であることを認識しなければなりません.すなわち,2倍移動するとグラフィックの重みが0になるので,2倍移動する場合を先に処理し,+1と−1の場合を見る.
では、+1と-1の順番をどう決めるのでしょうか.
一例から分かる.-1が先に表示された場合、4から6に移動すると、結果値は4->3->6になります.+1が先に現れると4->5->6となり、結果値は2となります.したがって,まず−1を考慮しなければならない.
💡 0-1 BFS
bfsまたはdfsを使用する場合、重みが同じグラフィックに適していることを前提とします.この問題では,0と1の2つの異なる重み付けが適用されるので,他の最短パスアルゴリズム−複数のアルゴリズムを用いる必要があり,一方,複数のアルゴリズムの時間的複雑さはO(ElogE)またはO(ElogV)である.ただし,この問題のように重みが0と1の場合,0−1 BFSを用いることができる.
0−1 BFSの時間的複雑度はO(V＋E)であった.論理構造はbfsと同じですが、キューではなくdequeが使用されます.重み値の小さい0はインデックスの先端に追加され,重み値の大きい1はインデックスの後端に追加される.このようにbfsを繰り返し使うと前の方がポップアップして使うので、重みが0の部分は先に処理して、値がもっと小さければ最高値に更新すればいいのです.
コメントブログ
📝ソースコード

import sys
input = sys.stdin.readline
from collections import deque

N, K = map(int, input().split())
max = 10**5
graph = [0]*(max+1)
visited = [False]*(max+1)
queue = deque()

def bfs(N):
    graph[N] = 1
    visited[N] = True
    queue.append(N)
    while queue:
        x = queue.popleft()
        if x==K:
            print(graph[x]-1)
            return
        for nx in (2*x, x-1, x+1):
            if 0<=nx<=max and visited[nx] == False:
                if nx==x*2:
                    graph[nx] = graph[x]
                    visited[nx] = True
                else:
                    graph[nx] = graph[x]+1
                    visited[nx] = True
                queue.append(nx)

bfs(N)