문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

a,b = map(int,input().split())
cnt = 1 #1을 더한값을 출력해야 하므로
while True:
    if a==b:
        break
    elif (b%2 !=0 and b%10 !=1) or b<a:
        cnt=-1
        break
    else:   
        if b%2 == 0:   #마지막 숫자가 1인 경우는 2로 나누어지지 않으므로 겹치지 않는다.
            b//=2	   #그래서 거꾸로 b에서 a를 만들때는 DFS/BFS 사용하지 않아도 풀 수 있다.
            cnt+=1
        else:
            b//=10
            cnt+=1
print(cnt)

BFS/DFS 사용하지 않고 구현할 수도 있다. B에서 1을 빼거나 2로 나누어서 A를 만들도록 한다.

BFS

from collections import deque
a,b = map(int,input().split())
result = -1
cnt = 1
q = deque([(a,cnt)])
while q:
    num,cnt = q.popleft()
    if num == b:
        result = cnt
        break
    elif num > b:
        continue
    q.append((num*2,cnt+1))
    q.append((num*10+1,cnt+1))

print(result)

BFS를 사용한 방법. 순회순서만 출력할 줄 알았는데 BFS로 여러가지를 할 수 있다는 것을 알 수 있었다. 뒤에 1을 붙이거나 2를 곱하는 두 가지 경우의 분기가 일어났을 때 각 결과를 큐에 담아서 가까운 수부터 모든 경우의 수를 탐색할 수 있다.

(https://alpyrithm.tistory.com/118 해당 페이지를 참고했습니다.)

DFS

a,b = map(int,input().split())

def dfs(i,cnt):
    if i >b:
       return
    elif i==b:
       print(cnt)
       exit(0)
    else:
        dfs(i*2,cnt+1)
        dfs(i*10+1,cnt+1)

dfs(a,1)
print(-1)

DFS로 구현했는데 확실히 코드는 간결해진다. 하지만 연산횟수는 훨씬 많아진다. 숫자가 조금만 커져도 overflow가 발생할 것.
print(dfs(a,1))로 하면 결과값이 None이 된다. 해당 함수가 직접 반환하는 값은 없어서 그렇다. dfs에서 return 값을 받아서 출력하려고 하면 쉽지가 않다. 몇번째에서 조건을 만족하는 값을 return 할 지 모르기 때문에. 그렇다고 모든 return 값을 저장할 순 없고 조건을 만족할 때 인자에 값을 저장하던지 아니면 바로 print시켜버릴수도 있다.

DFS는 재귀함수로 깊게 들어갔다가 결과 만족하지 못하는 함수는 return하고 스택에 있는것들을 하나씩 꺼내면서 수행한다.
결국에는 둘 다 탐색을 위한 알고리즘이고 DFS는 깊은 경우의 수까지 파고들어가는 반면 BFS는 가까운 경우부터 하나씩 탐색한다.
발생하는 경우의 수에 대해서 탐색해서 조건을 만족하는 값을 반환하는데 BFS는 가까운 것부터, DFS는 하나씩 깊이 들어가는 것이다.
그래서 웬만하면 최단거리를 찾는다거나, 가까운 값을 찾을때 BFS를 쓴다.
특정 경로가 존재하는지 찾는 등의 특수한 경우가 아니면 BFS를 쓰는게 스택 오버플로우도 안나고 시간도 덜 잡아먹는다.