BOJ_13549_숨바꼭질3

다익스트라(Dijkstra) 알고리즘을 사용해서 최단 경로를 찾는 문제

분기점은 5개로 잡았다

1. N < K
2. N > K -> 이 경우엔 뒤로 한 칸씩 총 N-K칸 이동만 할 수 있다
3. N == K -> 0
4. K가 N으로 나누어 떨어지고 몫이 2의 n제곱일 때
5. N이 0일 때 -> N = 1 일 때로 바꾼 후 + 1

따지고 보면 2개 정도만 핵심이다

몫이 2의 n제곱일 때

2*X를 하면 순간이동으로 0초 걸리기 때문에 4*x, 8*x ... 2^n*x는 모두 0초 걸린다

여기서 K / N 과 K / N - 1을 & 연산했을 때 만일 2의 n제곱이라면 0(False)이 나온다
왜냐면 & 연산 시 2의 n제곱의 자리를 0으로 바꾸고, 나머지를 1로 변경하기 때문이다
예를 들어 100(2) 에서 1 빼면 011(2) 이고 둘을 & 연산하면 모든 자리가 0이 된다

그렇게 확인해서 print(0) 해준다

N < K

2의 n제곱은 아니지만 2^n*x는 마찬가지로 0초 걸리기 때문에 이를 만족하는 모든 노드를 큐에 넣고 한 번에 돌렸다. 수가 큰 경우 빠르게 접근할 수 있기 때문이다
힙큐를 사용해서 시간이 낮은 순으로 노드를 정렬했다

# 뒤로 가는 로직이 있기 때문에 dp 보다 다익스트라가 적합  
# 출발 노드를 넣고 시간/위치를 갱신하면서 최단 거리를 찾는다  
# 가중치는 1 또는 X 이므로 양수값이라 다익스트라가 가능하다  
# 시간 복잡도는 O(100001 * log 100001) = 150만 정도 된다  
  
import heapq  
import sys  
  
N, K = list(map(int, input().split()))  
  
hq = list()  
d = [sys.maxsize] * 100001  
  
  
def dijkstra(n_idx, t):  
    if 0 <= n_idx <= min(100000, 2 * K - 1):  
        if d[n_idx] > t:  
            d[n_idx] = t  
            heapq.heappush(hq, (t, n_idx))  
  
  
def loop(start):  
    n = start  
    while n <= min(100000, 2 * K - 1):  
        d[n] = 0  
        heapq.heappush(hq, (0, n))  
        n *= 2  
  
    while hq:  
        # for i in range(K):  
        #     print(d[i], end=' ')        # print('')  
        tup = heapq.heappop(hq)  
        time = tup[0]  
        idx = tup[1]  
  
        if d[K] != sys.maxsize and time >= d[K]:  
            continue  
  
        dijkstra(idx - 1, time + 1)  
        dijkstra(idx + 1, time + 1)  
        dijkstra(2 * idx, time)  
  
  
if K < N:  
    print(N - K)  
elif N == K:  
    print(0)  
elif N == 0:  
    loop(1)  
    print(d[K] + 1)  
elif K % 2 == 0 and K % N == 0 and not (K // N) & (K // N - 1):  
    print(0)  
else:  
    loop(N)  
    print(d[K])