문제 링크: https://www.acmicpc.net/problem/16953

Thumbnail: Photo by Suhyeon Choi (Unsplash)

놀랍게도 그래프 탐색으로 풀 수 있습니다.

풀이

​처음 봤을때는 어떻게 풀어야 하는지 고민했는데, 태그에 그래프 탐색을 보자마자 방법이 떠올랐습니다.

엥? 이게 그래프 탐색이라고?

BFS(Breadth-First Search, 너비 우선 탐색)을 생각해봅시다. 큐를 기반으로, 현재 노드의 처리 과정에서 다음에 방문할 노드를 큐에 넣고, 다시 큐에서 하나 하나 꺼내가며 탐색합니다. 그렇다면, 굳이 방문할 다음 노드가 꼭 일반적인 그래프의 형태가 아니어도 되지 않을까요?

이 문제에서는 다음 노드 대신에 다음에 계산할 수를 넣어서 너비 우선 탐색을 진행할 수 있습니다. 다음에 계산해야 하는 수는 아래 2가지입니다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 
  • 어떤 수 \(X\)에 대해, \(X \times 10 + 1\)과 같습니다.

반복문의 종료 조건은 아래와 같이 설정할 수 있습니다.

• queue가 남아 있을 동안 반복하면서...
• 아래의 경우에 종료
  • 만약 현재 탐색중인 수가 \(B\)와 같다면
    • 이 때는 연산 횟수를 출력합니다.
  • 다음 탐색 후보가 전부 \(B\)보다 크다면
    • 이 때는 -1을 출력합니다.

전체 코드

from collections import deque
input = open(0).readline
A, B = map(int, input().split())
queue = deque(((A, 1),))
while queue:
    x, count = queue.popleft()
    if x == B:
        print(count)
        break
    if x * 2 <= B:
        queue.append((x * 2, count + 1))
    if x * 10 + 1 <= B:
        queue.append((x * 10 + 1, count + 1))
    count += 1
else:
    print(-1)

시행착오

연산 횟수를 원래 단일 전역 변수로 기록했는데, 막상 이렇게 하니 서로 다른 경우를 탐색하면서 무분별하게 수가 올라가 정답보다 아득히 많은 숫자가 나왔습니다.

그래서, 큐에 다음 탐색할 수를 추가할 때 동시에 해당 숫자 까지의 연산 횟수를 함께 기록해서 해결했습니다.