[BOJ-13913:鬼ごっこ4]

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

鬼ごっこ1題の論理ではパスを追加するだけで済むので簡単そうに見えますが、最初はどうやってパスを探せばいいのか迷っていました.

が問題に追加されたのは、記憶する前に探索されたパスである.木に思えばいい

結果を作成してキューに入れると、予め作成されたpath配列に結果を作成するために使用される親ノード(num)が保存されます.

キューで1つポップアップした場合、Kであるかどうかを確認します.

Kの場合、tempに一時保存し、1つの配列にプッシュし、path配列で親を検索します.

まで、親が見つかるまで上へ並べていきます.

の最初のpopのnum範囲を見つけることができます.また、tempとnが同じになるまでwhile文を書くこともできます.
p.s:整理してみると、for i in range(N,K-1,-1) ~~ returnは必要ない論理のようです.

コード#コード#

import sys
from collections import deque
N,K = map(int,sys.stdin.readline().split())

op_lst = [-1,1,2]

que = deque([[N,0]])
visited= [0 for _ in range(100001)]
path = [0 for _ in range(100001)]
def solve():
    if K<= N: # k가 n보다 작다면, 감소하는건 여기서 바로 처리.(n-k가 최소거리임.)
        print(N-K)
        for i in range(N,K-1,-1):
            print(i, end=" ")
        return
    while que:
        num,time = que.popleft()
        if num == K:
            print(time)
            p = [] # 정답 배열
            temp = num # 스위칭 할 temp
            for _ in range(visited[num]+1):
                p.append(temp)
                temp = path[temp]
            p.reverse()
            print(*p)
            break
        time+=1
        if num > 100000 or num < 0: # 시간 단축, num이 10만 넘어가면 굳이?, 0 미만은 위에서 거른다.
            continue
        for index in range(len(op_lst)):
            if index == 2:
                result = num * op_lst[index]
            else:
                result = num + op_lst[index]
            if 0 <= result < 100001 and visited[result]== 0:
                que.append([result,time])
                path[result]= num # path 배열에 현재 계산한 노드의 이전 노드를 설정
                visited[result]= visited[num]+1
solve()