[Python] 16953 - A → B

[Silver II] A → B - 16953 

[문제 링크](https://www.acmicpc.net/problem/16953)

🗝️알고리즘 분류

• 그래프 탐색
• 너비 우선 탐색

---

💻문제 정의

정수 A를 B로 바꾸려고 할 때, 연산의 횟수를 구하는 문제이다. 연산은 2를 곱하거나, 1을 가장 오른쪽에 추가한다.

 

💡접근 및 설계

너비 우선 탐색을 활용하여 문제에 접근하였다. A에서 2A, A1을 구한 후 B와 비교하고 횟수를 1 증가, B와 같을 때 까지 이를 반복하고, B일때의 연산 횟수를 출력한다. 연산 횟수는 visited 리스트에 저장하도록 한다.

 

처음 접근은 이랬지만, 문제에서 A와 B의 범위는 0 ~ 10^9이다. 10^9 길이의 정수 리스트는, 정수가 4B로 잡아도 4000MB라고 한다. 따라서 이 방법은 메모리초과를 일으킬 수 있으므로 다른 접근 방법을 생각해야 한다.

 

그래프 탐색을 진행할 때, A와 연산 횟수를 함께 저장하도록 하여 이 문제를 해결하였다.

 

✏️알고리즘 풀이

def bfs(start, end):
    count = 1

    Q = deque()
    Q.append([start, count])

    while Q:
        c, t = Q.popleft()

        for ix in [2 * c, int(str(c) + "1")]:
            if (ix == end):
                return t+1
            
            if (ix < end):
                Q.append([ix, t + 1])

처음 시작 점과 연산 횟수 count를 Q에 함께 추가한다.

c, t 두 변수 중 c에 연산을 적용하고 연산 후 end와 같다면 t+1을 반환한다.

c에 연산을 적용한 ix가 end보다 작다면, Q에 추가하고 연산 횟수를 더한다.

 

🗒️전체 코드

# 16953 A → B

from collections import deque

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

def bfs(start, end):
    count = 1

    Q = deque()
    Q.append([start, count])

    while Q:
        c, t = Q.popleft()

        for ix in [2 * c, int(str(c) + "1")]:
            if (ix == end):
                return t+1
            
            if (ix < end):
                Q.append([ix, t + 1])

result = bfs(A, B)
print(result if result != None else -1)

---