숨박꼭질 3 ( 13549번 )

13549번: 숨바꼭질 3

 

나의 풀이

import heapq
import sys

def _main(a, b):
    answer = [float('inf')] * 100001
    answer[a] = 0
    hq = [(0, a)]

    while True:
        now_cost, now_pt = heapq.heappop(hq)
        if (now_pt == b):
            return now_cost

        j_pt, p_pt, d_pt = (now_pt * 2), (now_pt + 1), (now_pt - 1)
        for next_pt in (j_pt, p_pt, d_pt):
            if (next_pt > 100000) or (next_pt < 0):
                continue

            next_cost = now_cost if (now_pt * 2 == next_pt) else (now_cost + 1)
            if (answer[next_pt] > next_cost):
                answer[next_pt] = next_cost
                heapq.heappush(hq, (next_cost, next_pt))

a, b = map(int, sys.stdin.readline().rstrip().split())
print(_main(a, b))

 

시간 복잡도

while True : 조건 만족시 까지 순회 ( 선형 시간 복잡도 )  
    now_cost, now_pt = heapq.heappop : heappop, push ( 로그 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )