[ 문제 ]

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

[ 알고리즘 유형 ]

그래프 이론
그래프 탐색
너비 우선 탐색

[ 정답 코드 ]

BFS
1)

from collections import deque
def bfs():
    q = deque([n])
    while q:
        x = q.popleft()
        if x == k:
            return d[x]
        for nx in [x-1, x+1, x*2]:
            if 0 <= nx < MAX and d[nx] == 0:
                d[nx] = d[x]+1
                q.append(nx)
n, k = map(int, input().split())
MAX = 100001
d = [0] * MAX
print(bfs())

2)
위의 코드는 방문체크와 최단거리를 기록하는 리스트를 하나의 리스트로 공용하여 사용했다. 분리해서 사용하는 것이 더 안전할 거 같아 분리했다.
그리고, 함수에서 main 값을 접근하는 것이 좋지 않을 것 같아 main에서 값을 출력하도록 수정했다.

from collections import deque
def bfs():
    check[n] = True
    dist[n] = 0
    q = deque()
    q.append(n)
    while q:
        now = q.popleft()
        for nxt in [now-1, now+1, now*2]:
            if 0 <= nxt <= MAX and check[nxt] == False:
                check[nxt] = True
                dist[nxt] = dist[now] + 1
                q.append(nxt)   

n,m = map(int, input().split())
MAX = 100001
check = [False]*(MAX+1)
dist = [-1]*(MAX+1)
bfs()
print(dist[m])

[ 풀이 방법 ]

수빈이가 동생을 찾는 가장 빠른 시간.
즉, 최단거리를 구하는 문제이다.
BFS로 해결하면 된다.