[알고리즘][Python] 백준 16953 A-->B 문제 풀이

문제 출처 : www.acmicpc.net/problem/16953

16953번: A → B

---

문제 해석 : A에서 B로 만드는데 2가지 방법을 사용할 수 있다. 

1. 수를 2배로 만든다.

2. 수의 끝에 1을 붙인다.

이때 최소 횟수로 B를 만드는 것에 +1 한 수를 반환해라, 만들 수 없다면 -1을 반환해라.

 

문제 풀이 : BFS로 가능한 모든 경우의 수를 체크하면 되는 문제이다.

---

풀이 코드

from collections import deque

def find_answer(A):
    visited = []

    Q = deque()
    Q.append([0,A])
    visited.append(A)

    while Q:
        count, num = Q.popleft()

        if num == B:
            return count + 1

        for next in (num * 2, int(str(num) + "1")):
            if next <= B:
                if next not in visited:
                    Q.append([count + 1, next])
                    visited.append(next)

    return -1

A, B = map(int, input().split())
answer = find_answer(A)
print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.