🧑🏻💻 문제링크
BFS
알고리즘으로 풀면 쉽게 풀 수 있는 문제이다. 하지만, 이동할 수 있는 방법이 3가지가 되기 때문에 어떻게 3가지의 방법으로 이동해야 하는지 알아야 되는 문제인 것 같다.
X-1 또는 X+1, 그리고 2*X 는 다음과 같이 나타낼 수 있다.
for next_node in (x-1, x+1, x*2):
from collections import deque
limit = 100001
N, K = map(int, input().split()) # N: 수빈이가 있는 위치, M: 동생이 있는 위치
arr = [0] * limit
def BFS(arr, N, K):
need_visit = deque()
need_visit.append(N) # 수빈이가 있는 현재 위치 추가
while need_visit:
node = need_visit.popleft()
# 동생이 있는 위치면 현재 위치를 반환
if node == K:
return (arr[node])
for i in (node+1, node-1, node*2):
if (0 <= i < limit) and arr[i] == 0:
arr[i] = arr[node] + 1
need_visit.append(i)
print(BFS(arr, N, K))