[python] 13549. 숨바꼭질 3

문제 출처

13549. 숨바꼭질 3

 

풀이

N, K = map(int,input().split())
if N > K:
    print(N-K)
elif N == K:
    print(0)
else:
    time = 0
    length = min(100001, K*2+1)
    visited = [0]*length
    q = []
    if N == 0:
        visited[0] = 1
        q.append(0)
    else:
        now = N
        while now < length:
            visited[now] = 1
            q.append(now)
            now *= 2

    while 1:
        if visited[K]:
            break
        nxt = []
        for i in q:
            if i > K:
                if 0 <= i-1 < length and not visited[i-1]:
                    nxt.append(i-1)
                continue
            for j in 1, -1:
                if 0 <= i+j < length and not visited[i+j]:
                    nxt.append(i+j)
        nxt = set(nxt)
        q = []
        for i in nxt:
            if i == 0:
                visited[0] = 1
                q.append(0)
                continue
            now = i
            while 1:
                if 0 <= now < length and not visited[now]:
                    visited[now] = 1
                    q.append(now)
                if now > K:
                    break
                now *= 2
        q = list(set(q))
        time += 1

    print(time)