[백준 | 파이썬] 16953 : A → B

💡 전형적인 bfs같아 보이지만, 메모리 초과를 고려해 다른 방법을 생각해 봐야 하는 문제!

문제

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

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

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

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

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

풀이 방법

1. 처음 생각한 풀이

• 전형적인 bfs 문제라고 생각했다. 2에서 시작한다면 다음으로 올 수 있는 값은 21과 4이다. 21과 4를 큐에 넣고 하나씩 꺼내서 연산을 반복하면서, visited 배열의 방문 인덱스에 +1 을 추가해주면 B번째 인덱스의 값을 구하면 답이 나온다. 그러나 입력의 범위가 10의 9제곱이어서 이 방법은 메모리 초과가 뜬다.

1. visited 배열 없이 풀 수 있는 방법을 고안해야 한다.

• visited 배열 없이 연산 횟수를 카운트하려면, 큐 안에 노드와 연산횟수를 묶어서 넣어주는 방법이 있다. 큐에서 요소를 하나씩 꺼낼 때마다 주어지는 노드와 연산횟수를 기준으로, 연산횟수를 +1 씩 더해간다.
• node가 B가 되는 순간 반복문을 탈출하고, 지금까지의 연산 횟수를 반환한다.

코드 - 1번 풀이

from collections import deque

a, b = map(int, input().split())
visited = [0]*(b+1)

def bfs():
    queue = deque()
    queue.append(a)
    visited[a] = 1
    while queue:
        node = queue.pop()
        nums = [node*2, int(str(node)+'1')]
        for i in nums:
            if i <= b:
                queue.append(i)
                visited[i] = visited[node] + 1
    return visited[b]

ans = bfs()
if ans == 0:
    print(-1)
else:
    print(ans)

코드 - 2번 풀이

from collections import deque

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

def bfs():
    queue = deque()
    queue.append((a, 1))
    while queue:
        node, cnt = queue.pop()
        if node == b:
            return cnt
        # print(node, cnt)
        nums = [node*2, node*10+1]
        for i in nums:
            if i <= b:
                queue.append((i, cnt+1))
    return -1

print(bfs())