[BOJ / PYTHON] 1697. 숨바꼭질

N, K = map(int, input().split())


def bfs(start, end):
    q = [start]
    checked = [0] * 200001
    checked[start] = 1

    while q:
        c = q.pop(0)

        if c == end:
            return checked[end] - 1

        for n in (c-1, c+1, c*2):
            if 0 <= n <= 200000 and checked[n] == 0:
                q.append(n)
                checked[n] = checked[c] + 1



ans = bfs(N, K)

print(ans)

풀이.

넓이 우선 탐색으로 문제를 해결한다.
현재 위치에서 탐색 가능한 경우의 수는 N-1, N+1, N*2 이다.
만약 다음 위치가 0보다 작거나 가능한 범위를 넘어가는 경우와 이미 방문한 경우는 제외한다.