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

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

import sys
input = sys.stdin.readline
from collections import deque

def bfs(n):
    q = deque()             # deque는 양쪽에서 입출력 가능
    q.append(n)             # q = deque([5])
    while q:
        now = q.popleft()     # 처음 시작점은 x = 5, q = deque([])
        
        if now == k:
            print(dist[now])
            break
        
        for nx in (now - 1, now + 1, now * 2):    # nx = 4, 6, 10인 3가지 경우로 각각 for문 돌아간다.
            if 0 <= nx <= 100000 and not dist[nx]:
                dist[nx] = dist[now] + 1
                q.append(nx)    # q = deque([4, 6, "10"])

dist = [0] * (100000 + 1)      # 이동하는 거리를 알기 위한 변수
n, k = map(int, input().rstrip().split())

bfs(n)

dist 배열을 이용해 인덱스에 대한 값이 걸리는 시간을 기록한다.
for nx in (now - 1, now + 1, now * 2)은 nx = 4, 6, 10인 3가지 경우로 각각 for문 돌아간다.
방문하지 않고 범위 안에 있으면 q에 삽입한다.
dist 배열을 한번 방문한 상태에서 한번 더 방문하면 이전 값이 현재 값보다 더 크기 때문에 비교할 필요가 없다.

dist[5]에서 4, 6, 10의 모든 케이스를 탐색한다. 그 중 dist[10]을 고르면 9, 11, 20의 값을 가지게 되고 dist[9]를 고르면 8, 10, 18의 값이 나온다. 마지막으로 dist[18]을 고르면 17, 19, 36에서 17이 추출된다.

참고
https://wook-2124.tistory.com/273