[백준 16953] A -> B -Python 풀이 (실버2)

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

16953번: A → B

---

문제

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

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

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

입력

첫째 줄에 A, B (1 ≤ A < B ≤ $10^9$)가 주어진다.

출력

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

---

풀이

BFS를 이용해서, 각 연산 방법을 다음에 방문할 정점으로 삼는다.

 이때 메모리 관리에 유의해야 한다. 일반적인 BFS 풀이처럼 방문 표시용 배열(visited)을 0부터 b+1까지 선언해주면 최대 $10^9$ 길이가 될 수 있으므로 메모리 초과가 발생할 수 있다. (visited를 a~b+1 까지만 선언하더라도 메모리 초과가 발생한다.)

 따라서 방문 표시 배열 대신에 q에 직접 방문 횟수를 저장해줘야 한다.

# 백준 16953 A->B 실버2 https://www.acmicpc.net/problem/16953
# 메모리초과
from collections import deque
a, b = map(int, input().split())
def bfs(start):

    q = deque([start])
    visited[start-a] += 1
    while q:
        x = q.popleft()
        if x == b:
            break
        
        for i in [2*x, int(str(x) + str(1))]:
            if i <= b and not visited[i-a]:
                q.append(i)
                visited[i-a] += visited[x-a] + 1
    return visited[b-a]

visited = [0 for _ in range(a, b+1)]
if bfs(a):
    print(bfs(a))
else:
    print(-1)

 위 코드는 Test case는 통과하지만 메모리 초과가 발생하는 코드이다. 아래의 코드가 정답 코드이다. q에 정점뿐만 아니라 cnt라는 방문횟수 카운트용 변수도 튜플로 함께 넣어줌으로써 메모리를 절약해준다. 

# 백준 16953 A->B 실버2 https://www.acmicpc.net/problem/16953
from collections import deque
a, b = map(int, input().split())
def bfs(start):
    q = deque([(start, 1)])
    while q:
        x, cnt = q.popleft()
        if x == b:
            return cnt
        
        for i in [2*x, int(str(x) + str(1))]:
            if i <= b:
                q.append((i, cnt+1))
    
if bfs(a):
    print(bfs(a))
else:
    print(-1)