문제 바로가기
문제 풀이
bfs순회로 경우를 찾되, 가장 작은 경우일 때를 출력한다.
최대 거리가 주어졌으니 해당 범위에 맞춰서 수를 미리 설정해둘 수 있다.
정답 코드
from collections import deque
N, K = map(int,input().split())
queue = deque()
queue.append((N, 0))
visited = [False] * 100001
result = 0
while queue:
num, count = queue.popleft()
if num == K:
print(count)
break
if 0 <= 2 * num <= 100000 and visited[2 * num] == False:
queue.append((2 * num, count + 1))
visited[2 * num] = True
if 0 <= num + 1 <= 100000 and visited[num + 1] == False:
queue.append((num + 1, count + 1))
visited[num+1] = True
if 0 <= num - 1 <= 100000 and visited[num-1] == False:
queue.append((num - 1, count + 1))
visited[num-1] = True
