문제

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

나의 코드

"""
1. 아이디어
bfs내 반복문에서 x-1, x+1, x*2하는 모든 경우에 대해 큐에 집어넣고 bfs를 돌려주면 된다.

2. 시간복잡도
O(n)
-> 일반적인 bfs의 시간복잡도는 O(V+E)이라 처음에 O(3n)이라 생각하고 상수는 무시할려고 했지만 
한번 방문한 노드는 재 방문하지 않기 때문에 O(n)이 맞다.
즉, 최대 간선의 수는 노드의 수를 넘지 않는다. 즉, |V| >= |E| 다.
"""

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

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

time = [0] * (100000+1) 
""" 움직인 위치별로 시간을 세는 변수로 (100000+1)로 제한한 이유는 
동생의 위치가 (0 ≤ K ≤ 100,000)로 나와 있기 때문에 
그 이상의 시간을 세는 것은 무의미 하기 때문이다. """

def bfs():
    q = deque([n])

    while q:
        px = q.popleft()

        if px == k: # 현재 위치와 동생의 위치가 같으면 시간을 return 한다.
            return time[px]

        for x in (px-1, px+1, px*2):
            # 100,000의 위치를 넘지 않고 방문한 기록이 없는 경우 실행한다.
            if 0 <= x <= 100000 and not time[x]: 
                # 이전 위치의 시간에 +1을 해줌으로써 시간을 갱신한다.
                time[x] = time[px] + 1
                q.append(x)

print(bfs())
    

느낀점

일반적(?) 으로 풀던 bfs 형식과는 조금 다른 문제여서 당황했다.
결국 bfs의 개념을 묻는 문제이기 때문에 어려움 없이 풀긴 했지만 문제를 많이 푸는게 중요 한거 같다.