[백준] 13549번 숨바꼭질 3 (by Python)

문제

2*X로 순간이동할 때만 0초가 걸린다는 점이 골머리를 앓게 만드는 문제. 그리고 시간을 더 줄이려면 앞으로 가는 수단은 +1과 *2 2가지가 있지만 뒤로 가는 수단은 -1 하나밖에 없다는 점을 이용해야 한다.

 

풀이

from collections import deque

n, k = map(int, input().split())

if n >= k:
    print(n - k)
else:
    q = deque([n])
    visited = [False] * 100001
    next_q = deque()
    answer = 0
    flag = True
    while flag:
        if not q:
            q = next_q
            next_q = deque()
            answer += 1
        temp = q.popleft()
        visited[temp] = True
        if 0 <= temp * 2 <= 100000 and k > temp:
            if temp * 2 == k:
                print(answer)
                break
            if not visited[temp * 2]:
                q.append(temp * 2)
        for i in range(2):
            nxt = temp + (-1) ** i
            if nxt == k:
                print(answer + 1)
                flag = False
                break
            if 0 <= nxt <= 100000:
                if not visited[nxt]:
                    next_q.append(nxt)

n이 k보다 크거나 같은 경우, -1씩 움직이는 수밖에는 없기 때문에 굳이 BFS를 활용하지 않도록 한다. 또, 거리가 0인 점들을 현재 큐에 추가하고자 2배씩 움직일 경우에 이미 k보다 커졌다면 더이상 2배씩 무의미해지기에 멈추어야 한다.