📚 1697-鬼ごっこ

かくれんぼをする
 

理解する

現在のポイント:Nに対して
妹の痣:Kに行けばいい.next_n = N (+- 1) or (*2)next nがKに到達したら,数秒出力すればよい.
これはbfsを起点に探索を行い,弟の点に着いたらすぐに終了すればよい.(小さい頃から探して、それから出てきて終わりましたが、大きいのを探す必要はないので)
 

ソース

import sys
from collections import deque

read = sys.stdin.readline

n, k = map(int, read().split())


# bfs

def bfs():
    queue = deque()
    queue.append((n, 0))
    visited = [False] * 100010
    visited[n] = True

    while queue:
        x, cnt = queue.popleft()

        if x == k:
            # bfs 특징 상 작은 것부터 검색 하니, 나오면 종료하면 된다.
            print(cnt)
            break

        for move_data in (x - 1, x + 1, 2 * x):
            if 0 <= move_data <= 100000 and not visited[move_data]:
                visited[move_data] = True
                queue.append((move_data, cnt + 1))


bfs()

 
採点結果