백준 1697 숨박꼭질 실버1 파이썬

이 문제에서 제일 중요한 포인트는 문제 푸는 핵심 전략이 아닌 제한 범위이다.
수빈이가 갈 수 있는 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000) 이 100000 를 방어 변두리로 잡는 것이 이 문제의 핵심 포인트 였다. 앞으로 제한 조건을 좀 더 잘 활용해야함을 잊지 말자.

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

구현

import collections
import sys

sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline


def iinput(): return int(input())


def lisinput(): return list(map(int, input().split()))


def dq(a):
    return collections.deque(a)


def minput(): return map(int, input().split())


def liinput(): return list(map(int, list(input())))


def addNode(a, b):
    return [a[0] + b[0], a[1] + b[1]]


def returnValue(graph, node):
    return graph[node[0]][node[1]]


def transpose(graph):
    return list(map(list, zip(*graph)))


if __name__ == '__main__':
    n, k = minput()

    will_visit = collections.deque([[0, n]])
    will_node = [n]

    while will_visit:
        if n == k:
            print(0)
            break
        travel = will_visit.popleft()  # 56
        travel[0] += 1
        move1 = [travel[0], travel[1] + 1]
        move2 = [travel[0], travel[1] - 1]
        move3 = [travel[0], travel[1] << 1]
        if move1[1] == k or move2[1] == k or move3[1] == k:
            print(travel[0])
            break

        if move3[1] > 0 and move3[1] <= 100000 and move3[1] not in will_node:
            will_visit.append(move3)
            will_node.append(move3[1])
        if 0 <= move1[1] <= 100000 and move1[1] not in will_node:
            will_visit.append(move1)
            will_node.append(move1[1])
        if move2[1] >= 0 and move2[1] not in will_node:
            will_visit.append(move2)
            will_node.append(move2[1])