백준 13549번: 숨바꼭질 3

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

13549번: 숨바꼭질 3

---

from collections import deque
n,k=map(int,input().split())

INF=int(1e9)
dist=[INF]*100001

def bfs():
    queue=deque()
    queue.append(n)
    dist[n]=0
    while queue:
        x=queue.popleft()
        if x==k:
            return dist[x]
        for nx in (x*2,x+1,x-1):
            if nx>=0 and nx<100001 and dist[nx]==INF:
                if nx==(x*2):
                    dist[nx]=dist[x]
                    queue.appendleft(nx)
                else:
                    dist[nx]=dist[x]+1
                    queue.append(nx)

print(bfs())

bfs를 이용해서..

방문하지 않은 x*2의 위치, x-1의 위치, x+1의 위치를 탐색하는데,

x*2로 순간이동할 때 0초가 들기 때문에 x*2를 우선적으로 하도록해서.. appendleft를 사용함