[백준 - 16953] A -> B - Python

분류: 1차원 bfs /

문제

문제 링크

문제 설명

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

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

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

입력

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

출력

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

 

풀이

- A에서 B로 BFS

from collections import deque

A, B = map(int, input().split())

hash = dict()
hash[A] = 0
q = deque([A])
ans = -1
while q and ans < 0:
    x = q.popleft()
    for y in [2*x, 10*x+1]:
        if (y > B) or (y in hash):
            continue
        if y == B:
            ans = hash[x] + 1
            break
        hash[y] = hash[x] + 1
        q.append(y)

if ans < 0:
    print(-1)
else:
    print(ans+1)

문제의 조건 대로 A에서 시작해 매 분기마다 2개의 연산을 수행하며 모든 경우를 BFS로 탐색한다. 이진트리에서 가장 먼저 도착한 깊이가 답이다. 

이때 각 숫자에 처음 도착한 연산 수가 최소이므로 한번 도착한 숫자의 최소 연산 수는 업데이트하지 않는다. 이를 위해 해쉬테이블에 도착한 숫자들과 각 숫자의 최소 연산 수를 저장한다.

내려오는 연산이 없으므로 연산 후 값이 B 보다 크면 무시, B와 같으면 탐색 성공.

 

- B에서 A로 탐색 방향 역전

A, B = map(int, input().split())
count = 1

while B > A:
    if B & 1 == 0:
        B //= 2
    elif B % 10 == 1:
        B //= 10
    else:
        break
    count += 1

if A != B:
    count = -1

print(count)

편의를 위해 출발지 집합을 X, 도착지 집합을 Y라 하자. x∈X이고 y∈Y이다.

x에서 y로의 최단 경로는 y에서 x로의 최단 경로와 같다. 이 문제의 경우 y에서 x로 가는 경로르 찾는 것이 더 빠르다.

모든 최소 연산 횟수를 구하는 문제에서 뒤집어서 푸는 것이 빠른 것은 아니다.

이 문제에서 뒤집어서 경로를 찾는 것이 빠른 이유는 x가 y에 대한 함수이기 때문이다.

• y가 짝수라면 `×2`연산이 수행된 것이고 `÷2`로 x를 특정할 수 있다.
• y의 1의 자리가 1이라면 `x10 +1`연산이 수행된 것이고 `-1 ÷10`으로 x를 특정 할 수 있다.
• 둘다 아니라면 y는 두 연산의 치역이 아니다.

x에서 y로의 탐색은 이진트리로 경우의 수가 지수적으로 증가했다.

y에서 x로의 탐색은 x=f(y)함수를 따라가면 되므로 탐색범위의 차원이 선형으로 낮아진다.