[백준][Python][13549][BFS] 숨바꼭질 3

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

13549번: 숨바꼭질 3

BFS 문제다.

 

나중에 발견하고 풀었는데, 기존 1,4와는 다른 문제여서 고생했다.

 

이 문제는, 2*X를 하는 순간이동은 시간이 소요되지 않는다.

따라서, X-1, X+1 이동의 경우는 append 를 통해 큐의 뒤에 추가해야 하고,

2*X의 경우에는 appendleft 를 통해 큐 앞에, 현재 탐색 상태에서 탐색을 해야한다.

또한, 큐에다 (현재위치, 현재 소요시간) 을 넣어주고, 2*X의 경우에는 소요시간 + 1 을 하지 말아야 한다.

(deque 를 사용한다고 가정한다.)

 

from collections import deque

n,k = [int(i) for i in input().split()]
q = deque()
v = [False]*200001

ret = 9123412341
q.append((n,0))

while q :
    cur = q.popleft()
    v[cur[0]] = True
    
    if cur[0] == k:
        if ret >= cur[1]:
            ret= cur[1]
        else:
            break
    
    if cur[1] > ret:
        break

    if cur[0]*2 <=200000 and not v[cur[0]*2] :
        q.appendleft((cur[0]*2, cur[1]))
    if cur[0]-1 >=0 and not v[cur[0]-1] :
        q.append((cur[0]-1,cur[1]+1))
    if cur[0]+1 <=200000 and not v[cur[0]+1] :
        q.append((cur[0]+1,cur[1]+1))


print(ret)