2022.02.13 [백준] (python 파이썬) 숨바꼭질3

 

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

13549번: 숨바꼭질 3

 

---

풀이

이 문제는 다른 숨바꼭질 문제와 다른게 가중치가 다른 문제이다 순간이동을 하면 가중치가 0이고 다른 상황은 가중치가 1이다. 가중치가 0인 상황은 먼저 계산해 주어야 하기 때문에 appendleft를해서 덱의 앞에 추가한다. 그래서 모든 상황에서 X*2를 우선적으로 생각해준다.

from collections import deque
 
n,k=map(int, input().split())
 
#해당 인덱스 값에 도달하기 위한 최단 거리 기록
arr=[-1]*(10**5+1)
 
def bfs(start,end):
    deq=deque()
    deq.append(start)
    arr[start]=0
    while deq:
        X=deq.popleft()
        if X==end:
            break
        if 0<2*X<=100000 and arr[2*X]==-1:
            arr[2*X]=arr[X]
            deq.appendleft(2*X)
        if 0<X+1<=100000 and arr[X+1]==-1:
            arr[X+1]=arr[X]+1
            deq.append(X+1)
        if 0<=X-1<=100000 and arr[X-1]==-1:
            arr[X-1]=arr[X]+1
            deq.append(X-1)
 
 
bfs(n,k)
print(arr[k])