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

 

 

# 동생을 찾을 수 있는 가장 빠른 시간. => 최소 거리. BFS
# 걷는다면 x-1/ x+1. 순간이동은 2*x. 시간은 모두 1초. 
# 큐에 뭔가 있다면 k인지 아닌지 확인
# 아니라면 이동방법만큼 반복. 이동했을때 인덱스 범위 내에 있어야하고 방문하지 않았어야함 
# 걸린 시간을 visited에 추가하고 1초 추가 + 큐에 추가 

from collections import deque
n, k = map(int, input().split())
m = 10 ** 5 # 최대 범위
visited = [0] * (m + 1) # 방문 기록

def bfs(start):
    queue = deque([start]) # 큐에 현재 위치를 인큐
    while deque:
        x = queue.popleft() # x = 현재 위치
        if x == k: # 만약 현재 목표지점에 도착했다면 
            print(visited[k]) # 방문 기록 출력 및 반복문 종료
            break
        for i in (x + 1, x - 1, x * 2): # 걷기, 순간이동 반복
            if 0 <= i <= m and not visited[i]: # 인덱스 범위 내에 있고 아직 미방문이라면
                visited[i] = visited[x] + 1 # 이동한 위치에 이동시 걸린 시간 입력
                queue.append(i) # 큐에 추가
        
bfs(n) # 현재 위치부터 탐색 시작

 

 

 

 

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

1697번: 숨바꼭질