[Python] 백준1697번 : 숨바꼭질

💡문제

백준 1697번 문제 링크

🍀풀이

이 문제는 1차원에서의 BFS 문제이다. 여태는 상하좌우로 퍼져나가서 2차원이었다면, 이거는 x-1, x+2, x*2로 1차원이다.

# 1차원에서의 BFS
import sys
from collections import deque
input = sys.stdin.readline

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

dist = [0] * 100001

def bfs(x):
    queue = deque()
    queue.append(x)
    
    while queue:
        x = queue.popleft()
        if x == k:
            return dist[x]
        for i in (x+1, x-1, x*2):
            if 0 <= i <= 100000 and not dist[i]:
                dist[i] = dist[x] + 1
                queue.append(i)

print(bfs(n))