[백준-실버1] 16953번 A -> B (BFS, 파이썬)

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

16953번: A → B

 

<내 코드>

- 숫자 a가 주어지고 b까지 가기 위한 최소 연산 횟수를 구하는 것이다.

- 연산은 2가지 종류가 있다.

   - 2를 곱한다.

   - 숫자의 오른쪽에 1을 추가한다.

- bfs를 이용해서 거리를 계산했다.

- 거리를 측정할 dist를 딕셔너리로 선언하였다.

  --> 이 때 리스트를 사용하고 크기를 b +1로 지정하면 메모리초과가 발생한다. (b는 최대 10**9 이기때문)

- bfs에서 처음 큐에 a를 삽입하고, 딕셔너리에 a를 키로 갖고, 값은 1을 넣어준다.

- 큐에서 뽑으면서 x에 대입한다. 이 때 반복문은 두가지 연산에 대해 수행한다.

- nx가 b보다 작거나 같은 경우에만 진행을 하는데 b보다 숫자가 커지면 작아지는 연산이 없기 때문이다.

- 그리고 nx가 딕셔너리에 없는 경우(처음 방문한 경우)에 dist[nx]에 dist[x] +1 을 대입하여 거리를 업데이트한다.

- 그 후 nx를 큐에 삽입하여 bfs를 수행한다.

 

- 최종 출력은 dist 딕셔너리에 b가 있는 경우 그 값을 출력하고, 없는 경우는 a->b로 만들 수 없기 때문에 -1 출력.

from collections import deque
a, b = map(int, input().split())
dist = {}

def bfs():
    queue = deque()
    queue.append(a)
    dist[a] = 1
    while queue:
        x = queue.popleft()
        for nx in [x*2, int(str(x) + '1')]:
            if 0<=nx <=b:
                if nx not in dist: #아직 방문 안했다면
                    dist[nx] = dist[x]+1
                    queue.append(nx)
bfs()
if b in dist:
    print(dist[b])
else:
    print(-1)