[Python] A→B(BFS) (백준 16953번 파이썬)

문제

정수 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

 

문제 이해

https://monamigoon.tistory.com/entry/Python-A%E2%86%92B-%EB%B0%B1%EC%A4%80-16953%EB%B2%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[Python] A→B (백준 16953번 파이썬)

- 백준 16953번을 그리디로 푼 후, BFS로 시도해보았습니다.

- 아래 그림을 보면 바로 이해가 될 것 같습니다.

- a,b가 주어질 때, a에 대해 모든 연산을 진행합니다. 연산시에 노드 레벨 값(연산 횟수)을 함께 기록합니다.

- 해당 연산이 진행된 값이 b보다 작은(범위 내) 값이라면, 큐에 해당 값을 추가하여 연산을 계속 진행합니다.

- 연산을 진행한 값이 b보다 큰 값이라면 불가한 경우이므로 큐에 넣지 않습니다.

- a와b가 같아지거나 큐가 비게되어 반복문이 종료되었을 때, a와 b가 같다면 문제 조건대로 레벨 +1 값을 출력합니다.

- 같지않다면 -1을 출력합니다.

 

 

코드

#백준 16953 A->B

from collections import deque

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

q = deque()

level = 0

q.append((a,level))

while q and a!=b:

    a, level = q.popleft()

    if a*2 <= b:

        q.append((a*2, level+1))

    if a*10+1 <= b:

        q.append((a*10+1, level+1))

if a==b:

    print(level+1)

else:

    print(-1)