백준 / A → B / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: A → B(BFS)

문제 사이트: https://www.acmicpc.net/problem/16953

16953번: A → B

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

38096

15757

12583

39.931%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2 162

예제 출력 1 복사

5

2 → 4 → 8 → 81 → 162

예제 입력 2 복사

4 42

예제 출력 2 복사

-1

예제 입력 3 복사

100 40021

예제 출력 3 복사

5

100 → 200 → 2001 → 4002 → 40021

---

나의 풀이

BFS 를 사용하면 빠르게 풀 수 있다! 연산 결과가 목표값 B보다 작다면 새로운 연산(곱하기와 맨끝에 1 삽입)을 추가하여 연산 횟수를 큐에 넣고, 연산 결과가 목표 값과 같다면 answer에 저장한다.

 

answer에서 연산횟수가 가장 적은 순으로 정렬하고 출력하면 답이 나온다.

반대로, 연산 결과가 목표 값과 같은 경우가 없으면 빈 answer 리스트가 반환되므로, 이 경우에는 -1을 출력한다.

 

from collections import deque
import sys
input = sys.stdin.readline
a,b= map(int,input().split())

queue = deque()
queue.append([a,1])
answer = []
while queue:
    q = queue.popleft()
    result = [[q[0]*2,q[1] + 1],[q[0]*10 + 1, q[1]+1]]
    for i in result:
        if i[0] == b:
            answer.append(i)
        elif i[0] < b:
            queue.append(i)
answer.sort(key = lambda x:x[1])
if answer:
    print(answer[0][1])
else:
    print(-1)