[파이썬/Python] 백준 16953번: A → B

숨·2024년 7월 20일

코테

알고리즘 문제 풀이

목록 보기

39/105

📌 문제 : 백준 16953번

📌 문제 탐색하기

A, B : 입력된 정수 ( $1 ≤ A < B ≤ 10^9$ )

✅ 입력 조건
1. A, B 공백 구분해 입력
✅ 출력 조건
1. 2가지 연산 방법 이용해 A → B로 바꾸는데 필요한 연산 최솟값에 1을 더한 값 출력

2가지의 연산이 있다.
1. 2 곱하기
2. 1을 수의 가장 오른쪽 추가

2가지 연산을 최소로 사용해서 A를 B로 만들어야 한다.
2를 곱하는 연산은 숫자를 짝수로 만들고, 1을 추가하는 방법은 숫자의 끝자리는 1로 만든다.
이 점을 기반으로 B에서 A가 되는 과정을 역추정할 수 있다.

B가 짝수라면 2로 나누고, 1로 끝난다면 문자열로 변환해 맨 뒤의 1을 제거한다.
그 후에도 조건에 따라 A가 될 때까지 연산을 반복하며 횟수를 센다.

연산 후 나온 숫자가 A보다 작다 → A를 B로 만들 수 없다는 의미이므로 -1을 출력한다.
연산 후 나온 숫자가 A가 되었다 → 횟수에 1을 더한 수를 출력한다.

가능한 시간복잡도

조건에 따라 2가지 연산 수행 → $O(1)$
BFS 수행 → $O(B)$

최종 시간복잡도
$O(B)$ 으로, 최악의 경우에도 1초 내로 계산이 가능할 것 같다.

알고리즘 선택

B가 A 될 때까지 조건에 따라 BFS로 연산 수행

📌 코드 설계하기

A, B 입력
BFS 정의
2-1. 방문 처리
2-2. 큐가 빌 때까지 반복
2-3. 현재 값에서 조건에 따라 연산 수행
BFS 수행
결과 출력

📌 시도 회차 수정 사항

1회차

# A, B 입력
A, B = map(int, input().split())

temp = B
count = 0

while True:
    if temp == A:
        print(count + 1)
        break

    elif temp < A:
        print(-1)
        break

    elif temp % 2 == 0:
        temp //= 2
        count += 1

    elif str(temp)[-1] == '1':
        temp = int(str(temp)[0:-1])
        count += 1

결과
while문으로 연산 과정을 거치도록 구현했더니 시간 초과가 발생했다.
$1 ≤ A < B ≤ 10^9$ 라는 범위를 보고 예상은 했지만 while문을 사용하니 바로 초과가 발생했다.
따라서 BFS를 구현했다.

2회차

# BFS 구현
def bfs(x):
    queue = deque([(x, 1)])
    # 큐가 빌 때까지 반복
    while queue:
        x, count = queue.popleft()

        if x == A:
            return count

        if x < A:
            return -1

        if x % 2 == 0:
            x //= 2
            count += 1
            queue.append((x, count))

        if str(x)[-1] == '1':
            x = int(str(x)[0:-1])
            count += 1
            queue.append((x, count))

결과
연산 후 A보다 작은 값이 나오면 -1을 바로 리턴하도록 구현했더니 틀렸다고 나왔다. continue를 작성하고 전체 함수의 리턴값을 -1로 했더니 이 에러는 해결되었다.
바로 return -1을 하게 되면 모든 탐색이 완료되기 전에 탐색을 종료될 수 있어 잘못된 결과를 얻을 수 있기 때문에 틀린 것 같다.

3회차

# BFS 구현
def bfs(x):
    queue = deque([(x, 1)])
    # 큐가 빌 때까지 반복
    while queue:
        x, count = queue.popleft()

        if x == A:
            return count

        if x < A:
            continue

        if x % 2 == 0:
            x //= 2
            count += 1
            queue.append((x, count))

        if str(x)[-1] == '1':
            x = int(str(x)[0:-1])
            count += 1
            queue.append((x, count))

    return -1

결과
큐에 다음 상태의 값을 append할 때 미리 값을 수정한 후에 추가해주니 ValueError가 발생했다.
BFS는 동일한 레벨의 모든 상태를 한꺼번에 탐색하므로, 어떤 상태에서 다음 상태로 갈 때, 해당 상태를 큐에 추가하여 동시 탐색이 이루어지게 한다. 직접 수정하면 현재 상태만 업데이트되므로 레벨 구분이 명확하지 않게 되어 ValueError가 발생하는 것이다.
최단 경로를 보장하는 BFS에서, 값을 직접 수정해 다음 상태로 넘어간다면 동일한 상태를 여러 번 방문하게 될 수 있어 최단 경로를 보장하지 않게 된다.
직접 수정하지 않고, 큐에 다음 상태를 넣어주는 식으로 변경하여 해결하였다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# A, B 입력
A, B = map(int, input().split())


# BFS 구현
def bfs(x):
    queue = deque([(x, 1)])
    # 큐가 빌 때까지 반복
    while queue:
        x, count = queue.popleft()

        if x == A:
            return count

        if x < A:
            continue

        if x % 2 == 0:
            queue.append((x // 2, count + 1))

        if str(x)[-1] == '1':
            x = int(str(x)[0:-1])
            queue.append((x, count + 1))

    return -1


# BFS 수행
result = bfs(B)

# 결과 출력
print(result)