문제

https://www.acmicpc.net/problem/13549

소스코드

import sys
from collections import deque
input = sys.stdin.readline
if __name__ == "__main__":
    n, k = map(int, input().split())
    visited = [-1 for _ in range(100001)]
    visited[n] = 0
    q = deque()
    q.append(n)

    while q:
        x = q.popleft()
        if x == k: #먼저 찾으면 그냥 끝남
            break
        for i in [x-1,x+1,x*2]:
            if 0 <= i < 100001:
                if i == x*2:
                    if visited[i] == -1:
                        visited[i] = visited[x]
                        q.appendleft(i)
                else:
                    if visited[i] == -1:
                        visited[i] = visited[x] + 1
                        q.append(i)
    print(visited[k])

설명

최단거리를 찾는 문제 -> BFS
최단거리를 메모이제이션하여 가장 적은 값을 출력해준다.
Q에 먼저 넣어서 먼저 원하는 값을 출력하면 되므로 기존보다 값이 작으면 메모이제이션 값 교체 이런거 없음

순간이동을 했다고 했으니까 appendleft를 통해서 먼저 탐색해준다.