[백준] 13549번: 숨바꼭질 3

https://www.acmicpc.net/problem/13549

initial

Ok so there was an obvious 3^n solution but i was confused with how time complexity was confused. If we have a range from 0 to 100k, if we visit the value just once, no matter which algorithm we use it will be o(n).

So whilst there are 3 options for each traversal value, and I thought i should not do it cuz it is 3^n, I was wrong.If the question logic ensures that we get the right value if we just can visit the value once (if not visited[n]), then time complexity is no longer 3^n but n - regardless of the 3 actions we take and 3 values that we put in our deque.

So we can do bfs.

One optimisation is we wanna prioritise teleporation cuz we dont have to increment count and we want minimal count. So instead of append(), we use appendleft() to put that teleporation move to the left of our deque. Ohhh for normal moves of +1 and -1, it just uses append to append to the right of the queue but for teleportation of 2*cur_position, it uses appendleft() to append to left of queue to be processed first before others.

Another optimisation that does the above automatically is using dijkstra. Since dijkstra uses heap, we can place count as the 0th index in our heap and the changing value (cur_num) in the 1st index and wrap them as a tuple. Heap will automatically pop the tuple with least count so that is smart.

my solution

from collections import deque

N, M = map(int, input().split())
queue = deque([(N, 0)])
max_check = 100001
check = [False for _ in range(max_check)]
check[N] = True
ans = [max_check for _ in range(max_check)]

while queue:
    cur_num, cur_count = queue.popleft()
    if cur_num == M:
        print(cur_count)
        exit()
    for i in range(cur_num - 1, cur_num + 2):
        if i == cur_num:
            if 2 * i < max_check and not check[2 * i]:
                queue.append((2 * i, cur_count))
                check[2 * i] = True
        else:
            if 0 <= i < max_check and not check[i]:
                queue.append((i, cur_count + 1))
                check[i] = True

opti

to optimise, use appendleft() for teleportaiton (2*i)

or u can use dijkstra like

https://seen-young.tistory.com/88

complexity

not 3^n but n time

n space