내 코드

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

start, finish = map(int, input().split())
explored = set()
q1 = deque([start])
def bfs(q1: deque, time_lapse: int):
    q2: deque = deque()
    while q1:
        v = q1.popleft()
        if v == finish:
            print(time_lapse)
            return
        if v not in explored:
            explored.add(v)
            for i in [v+1, v-1, v*2]:
                if i >= 0 and i <= 100000:
                    q2.append(i)
    bfs(q2, time_lapse+1)
    
bfs(q1, 0)

메모리: 136492 KB, 시간: 388 ms

1. 두 개의 deque를 사용했다.
2. 첫번째 큐에 시작점을 넣고 함수를 호출하며 시작한다.
3. 주변 지점 ([v+1, v-1, v*2])에 대해 범위를 벗어나지 않는지 확인하며 두번째 큐에 추가한다.
4. 두번째 큐와 1이 올라간 time_lapse를 bfs 함수에 되먹여 호출해 재귀한다.
5. 마치는 지점 finish가 큐에서 나올 때 시간이 얼마나 지났는지 time_lapse를 출력하고 종료한다.

크게 어렵지 않은 로직이다. 문제 그대로 풀어 구현할 수 있는 코드이다. 다만 마지막 for 반복문에서 i의 범위를 지정해주지 못해 메모리 초과 에러로 고생했다. 아래 코드에 비해 시간, 공간복잡도가 크다. 아래 코드보다 재귀의 깊이도 훨씬 깊다.

다른 코드 분석

탑다운 방식의 다이나믹 프로그래밍 기법을 사용한 jyl4you 님의 코드를 보자:

import sys
def f(n, k):
    if n >= k:
	    return n - k
    if k == 1:
	    return 1
    if k % 2:
	    return min(f(n, k+1), f(n, k-1)) + 1     
    return min(k-n, f(n,k//2)+1)
print(f(*map(int,sys.stdin.readline().split())))

메모리 약 31MB, 시간 36ms

1. n 이 k 보다 같거나 크면 n - k를 반환한다. 움직이지 않아도 되거나 뒤로 한칸씩 가는 수밖에 없기 때문이다.
2. k가 1이라면 1을 반환한다. 1번 경우를 제외하면 n이 0인 경우밖에 없다. 0에서 1로 가는 경우이므로 1을 반환. 3, 4번 조건으로 처리하지 못하는 경우다?
3. k가 2로 나누어 떨어지지 않는다면, k의 주변값에 대해 재귀하고, 둘 중 더 작은 값에 1을 더하여 반환한다.
   • 이 때 주변 값은 2로 나누어 떨어지므로 1, 2, 4번 단계가 호출된다.
   • 1을 더하는 이유는 k에서 한걸음 떨어진 값이기 때문이다.
4. 그렇지 않다면 k-n과 k를 2로 나눈 값을 되먹인 함수 + 1 중 더 작은 값을 반환한다.
   • 2로 나눈 값에 대해선 1을 더해준다. 순간이동(*2)을 한번 했다는 뜻이다.
   • k-n : n에서 k로 한 걸음씩 왔다는 뜻. 순간이동 한 것보다 이 값이 더 작으면 이 값을 반환한다. 왜 이 값인가? k가 2로 나누어 떨어질 때, 한 걸음씩 가는 방법과 그것을 2로 나눈 값에 한 걸음씩 가는 방법이 있다. 여기서 k는 k//2로 되먹여지고 그 주변 값에 대해 3번을 수행하거나 다시 4번을 수행하게 될 것이다. 그 값이 f(n,k//2)로 반환되는데 한 번 순간이동을 했으니 1을 더한다. n과 k//2에 대해서도 반복 수행.
   • f(n, k//2)함수가 호출되었을 때 k//2가 2로 또다시 나누어 떨어진다면 나눌 때마다 1씩 더해진 값이 반환될 것이며, k//2가 2로 나누어 떨어지지 않는 순간에 대해서 k-n이 반환될 것이다.
   • 예를 들어, k = 10, n = 2인 경우, 처음 f(2, 10)가 실행되고 4번 케이스에서 f(2, 5)가 실행된다. 5는 홀수이므로 3번 케이스 진입, k가 4 또는 6인 경우에 대해 실행하는데, f(2, 4)는 1이고 (f(2, 2) + 1) f(2, 6)은 2이다 (f(2, 3) + 1).
   • 따라서 f(2, 5) = f(2, 4) + 1 = 2, f(2, 10) = f(2, 5) + 1 = 3이 된다.
   • 확인해보면 2, 4, 5, 10 으로 2에서 3단계를 거처 10까지 가는 것을 볼 수 있다.

나가면서

다이나믹 프로그램으로 풀 수 있을 것 같다는 생각이 들었지만 구현하지 못했다. 그만큼 아직 다이나믹 프로그래밍이 익숙하지 않다는 뜻일 것이다. 많이 연습해야겠다.