이 문제는 가장 빠른 시간에 대해 물어보고 있지만 사실상 최단경로를 구하는 문제이다.
걸리는 시간은 거리로 생각하고 기존의 최단경로 문제와 유사하게 풀이하면된다.
그렇기 때문에 bfs 알고리즘 방식으로 문제를 해결해주었다.
import sys
from collections import deque
n,k = map(int, sys.stdin.readline().split())
max_num = 100000
visited = [0]*(max_num+1)
def bfs():
q = deque()
q.append(n)
while q:
x = q.popleft()
#목표위치에 도착할 때
if x == k:
print(visited[x])
break
for j in (x-1,x+1,x*2):
if 0<=j<=max_num and visited[j]==0:
visited[j] = visited[x]+1
q.append(j)
return
bfs()보통 미로 문제에서는 dx=[-1,1,0,0] dy = [0, 0 ,1,-1] 이런식으로 한 후 for 문에서 상하좌우를 방문한다.
하지만 이 문제에서는 x-1, x+1, x*2 로 이동할 수 있으므로 for 문에서 이 세곳만 방문해주는 형식으로 코드를 작성해주면된다.
처음에는 이런 형태로 for문을 작성한 경험이 없어 이런 형태로 처리해줄 생각을 못했었는데
for j in (1,2,3):
print(j)이런식으로 작성한것과 동일하게 작동한다는 것을 이해한 후에는 쉽게 적용이 됐다. 그 후에는 기존의 최단경로 문제와 유사하게 해결해주면 된다.
