[백준] 1697번 숨바꼭질 / 파이썬(python)

# 문제 링크

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

1697번: 숨바꼭질

# Soultion

최소 시간을 구하기위해 bfs를 사용하였다.

from collections import deque
 
n,k = map(int,input().split())
queue = deque([n])
visited = [0]*100001
visited[n]=1
 
while(queue):
    a = queue.popleft()
    if a==k:
        print(visited[a]-1)
        break
        
    if 2*a<=100000 and visited[2*a]==0:
        queue.append(2*a)
        visited[2*a] = visited[a]+1
    if a+1<=100000 and visited[a+1]==0:
        queue.append(a+1)
        visited[a+1] = visited[a]+1
    if a-1>=0 and visited[a-1]==0:
        queue.append(a-1)
        visited[a-1] = visited[a]+1

 

4. bfs를 사용하기위해 queue를 생성한 뒤, 나의 위치를 넣어준다.

5. 위치별 최소시간을 보기위해 리스트 생성

6. 현재 나의 위치에 1을 넣어준다.

10. 만약 현재위치가 동생의 위치이면, 최소거리를 출력한다.

14 ~ 22. 2배, -1, +1의 경우를 각각 계산한다.