백준. 1697번. 숨바꼭질 파이썬 풀이

백준. 1697번. 숨바꼭질 파이썬 풀이

문제링크 https://www.acmicpc.net/problem/1697

dp&bfs를 사용하여 해결

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

from collections import deque

# 수빈이 n, 동생 k
n, k = map(int, input().split())

visited = [False] * 100001

queue = deque()

queue.append([n, 0])

while queue:
    now, time = queue.popleft()
    if now == k:
        print(time)
        break

    visited[now] = True

    if now-1 >= 0 and not visited[now-1]:
        queue.append([now-1, time+1])
    if now+1 <= 100000 and not visited[now+1]:
        queue.append([now+1, time+1])
    if now*2 <= 100000 and not visited[now*2]:
        queue.append([now*2, time+1])