[백준] 13549 숨바꼭질 3

📖 문제

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

💻 내 코드

from collections import deque
import sys
N, K=map(int, sys.stdin.readline().split())

mlist=[-1]*100001

def find(n): # bfs
    queue = deque()
    queue.append(n)
    mlist[n]=0
    while True:
        x=queue.popleft()

        if x == K:
            return
        for i in range(3):
            if i==0:
                nx=2*x
            elif i==1:
                nx=x+1
            elif i==2:
                nx=x-1
            if 0<=nx<100001 and mlist[nx]==-1:

                if i==1 or i==2:
                    mlist[nx]=mlist[x]+1
                    queue.append(nx)
                else:
                    mlist[nx]=mlist[x]
                    queue.appendleft(nx) # deque 맨앞에 삽입


find(N)
print(mlist[K])

💡 풀이

• bfs를 사용하기 위해서는 가중치가 같아야 한다
• 이 문제에서는 순간이동시에는 가중치가 0, 걸어갈 땐 가중치가 1로 가중치가 다른 문제
• 따라서 더 짧게 걸리는 순간이동을 먼저 수행하도록 deque의 왼쪽에 추가해준다
• 걸어갈 때는 원래대로 deque의 마지막에 append
• 이를 수행하다 K에 도달하면 멈춤
• K에 저장된 값 출력