[백준/Python] 13549 숨바꼭질 3

 

 

 

• BFS를 이용하여 풀었다.

 

from collections import deque

N,M = map(int,input().split())
used = [21e8] * 100001
result = []
def bfs(N,cnt):
    q = deque([(N,cnt)])

    while q:
        N,cnt = q.popleft()
        if 0 <= N < 100001:
            if cnt < used[N]: # used배열에 도착했을때 cnt의 최소값만 갱신
                used[N] = cnt 
            else:
                continue

            q.append([N-1,cnt+1])
            q.append([N+1,cnt+1])
            q.append([N*2,cnt])

bfs(N,0)
print(used[M]) # used 배열에는 시작점으로부터 각 1~100,000까지의 위치에 도착했을 때 
# 가장 시간이 적게 소요된 값만 있으므로 동생의 인덱스값을 출력해주면 된다.