숨바꼭질 2 ( 12851번 )

12851번: 숨바꼭질 2

 

나의 풀이

import sys, heapq

def _main(n, k):
    answer = 0
    visit = [int(1e9)] * 100001
    visit[n] = 0
    hq = [(0, n)]

    while hq:
        now_cost, now_point = heapq.heappop(hq)
        if (now_point == k):
            answer += 1
        else:
            for next_point in (now_point + 1, now_point - 1, now_point * 2):
                if (0 <= next_point < 100001) and (visit[next_point] >= now_cost + 1):
                    visit[next_point] = now_cost + 1
                    heapq.heappush(hq, (now_cost + 1, next_point))
    
    return f"{visit[k]}\n{answer}"
    
n, k = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, k))

 

시간 복잡도

while hq : n 번 반복 ( 선형 시간 복잡도 )
    heappop, heappush : 로그 시간 복잡도

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )