(Python) - BOJ(16953번) : A → B

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

16953번: A → B

---

• 문제 : 

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

 

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

 

 

 

---

• 풀이 :

주어진 수에서 2를 곱하거나 1을 가장 오른쪽에 추가하는 모든 경우를 BFS로 탐색하여 최소횟수를 구한다.

 

 

 

---

• 소스코드 : 

 

def bfs(A,B):
    queue = []
    queue.append([A])
    cnt = 0
    while queue[-1]:
        queue.append([])
        for i in queue[cnt]:
            if i == B:
                return cnt+1
            if i*10 + 1 <= B:
                queue[-1].append(i*10+1)
            if i*2 <= B:
                queue[-1].append(i*2)
        cnt+=1
    return -1
 
 
if __name__ == "__main__":
    A,B = map(int,input().split())
    print(bfs(A,B))