[파이썬] 백준 1697번: 숨바꼭질

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

1697번: 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

from collections import deque

def bfs(): # 최단 거리 구할때 사용
    q=deque([n]) # q = deque([5])
    while q:
        now_pos=q.popleft()
        if now_pos==k:
            return arr[now_pos]
        for next_pos in (now_pos-1,now_pos+1,now_pos*2): # next_pos = 4, 6, 10
            # next_pos가 범위 안이고, 아직 방문하지 않은 위치라면(arr[next_pos]==0)(알아서 해당 위치에 도달하는 최소시간이 됨)
            if next_pos>=0 and next_pos<MAX and arr[next_pos]==0:
                arr[next_pos]=arr[now_pos]+1
                q.append(next_pos) # q = deque([4, 6, "10"])
                

MAX=100001 # 시간초과 안나게 수 제한
n,k=map(int,input().split())
arr=[0]*MAX # 걸리는 시간 리스트
print(bfs())