[파이썬] 백준 16953번: A -> B (BFS, 최단거리)

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

16953번: A → B

 

문제

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

 

from collections import deque

A,B=map(int,input().split())
visited=set() # 방문 처리 집합 (해당 문제처럼 방문할수있는 수가 무한이면 배열대신 집합으로 처리) 
flag=False # 방법이 있는지 여부
q=deque()
q.append((A,0)) # 처음 숫자 A, count 0
while q:
    x,cnt=q.popleft()
    if x==B: # B에 도달하면 카운트 출력 후 break
        print(cnt+1)
        flag=True
        break
    if x>B: # x가 B보다 크면 더이상 진행할 필요없으므로 continue
        continue
    a=2*x # 1번 경우
    b=x*10+1 # 2번 경우
    if a not in visited: # 방문하지않았으면, q에 추가
        q.append((a,cnt+1))
        visited.add(a)
    if b not in visited:
        q.append((b,cnt+1))
        visited.add(b)

if flag==False: # 방법이 없으면 -1 출력
    print(-1)