문제 링크

풀이

• 도착할 수 있는 모든 위치의 도착하는 시간을 visit 리스트에 inf로 초기화
• 처음 위치를 0초로 지정하고 현재 위치에서 갈 수 있는 방법을 stack에 추가
• 각각의 방법을 수행하면 이전에 걸렸던 시간 + 1을 현재 위치에 저장

도움이 된 반례

1697번 숨바꼭질 반례 모음

10 19
답: 2

2*X의 위치로 갈 때의 범위를 nx * 2 <= k 로 해서 2*X 후 위치가 k 이상이 되고 -1로 도착했을 경우를 구하지 못했음. --> 범위를 nx * 2 <= 100000로 변경해서 통과

코드

import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())

visit = [float('inf')] * 200001
visit[n] = 0
answer = []
q = deque([n])
while q:
    nx = q.popleft()
    if nx == k:
        print(visit[nx])
        break

    if nx * 2 <= 100000 and visit[nx * 2] > visit[nx] + 1:
        q.append(nx * 2)
        visit[nx * 2] = visit[nx] + 1

    if nx > 0 and visit[nx - 1] > visit[nx] + 1:
        q.append(nx - 1)
        visit[nx - 1] = visit[nx] + 1

    if nx + 1 <= k and visit[nx + 1] > visit[nx] + 1:
        q.append(nx + 1)
        visit[nx + 1] = visit[nx] + 1 

맞왜틀 ㅠㅠ 하면서 엄청 제출했다.. 🤣