[BOJ / Python] 16953번: A → B

문제: BOJ 16953번

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

풀이

어디선가 많이 본 문제이다. 전형적인 그리디 알고리즘 문제!

우선 A와 B를 입력받아, 단순 재귀로 풀면 될 것 같다. 한번 해보자.

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


def bfs(x, t):
    if x == b:
        return t
    elif x > b:
        return -1
    else:
        bfs(x * 2, t + 1)
        bfs(x * 10 + 1, t + 1)


print(bfs(a, 1))

엄청 쉬운 문제잖아? 하고 그냥 무지성으로 적어서 확인도 안하고 제출했다.
바로 틀렸습니다 ㅋㅋ
예제를 돌려보니 None이 뜨더라.

문제는 else 문에서 어떠한 return도 없는것이었다.
확실히 군대갔다오니까 지성이 사라졌다.
그냥 문제만 보이면 대책없이 박는다...

두개의 재귀 결과를 비교해서 더 작은 값을 무조건 반환하게 해서

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


def bfs(x, t):
    if x == b:
        return t  
    elif x > b:
        return -1  
    else:
        # 재귀적으로 호출하고 결과를 받음
        result1 = bfs(x * 2, t + 1)
        result2 = bfs(x * 10 + 1, t + 1)

        # 두 결과가 모두 -1이면 -1을 반환
        if result1 == -1 and result2 == -1:
            return -1
        # 하나가 -1이면 다른 값을 반환
        elif result1 == -1:
            return result2
        elif result2 == -1:
            return result1
        else:
            # 두 값이 모두 유효하면 더 작은 값을 반환
            return min(result1, result2)


print(bfs(a, 1))

짠 일단 처리했다. 반성의 의미로 재귀는 갖다버리겠다...
덱으로 다시 풀어보자..

최종코드

from collections import deque

a, b = map(int, input().split())
d = deque()
d.append((a, 1))
ans = -1
while d:
    x, t = d.popleft()
    if x > b: # 더 크면 바로 -1을 리턴했던 첫 코드와는 차원이 다르다. 그냥 컨티뉴해버리면 끝이라니...
        continue
    elif x == b:
        ans = t
        break
    else:
        d.append((x * 10 + 1, t + 1))
        d.append((x * 2, t + 1))
print(ans)

짠..

내가 원래 머리로 생각했던 풀이는 이런 풀이인데, 덱이 뭔지 까먹어서 그냥 재귀로 해버린 듯 하다...

아! BFS로 풀어야할거같이 생겨서 BFS가 재귀로 하는거였나...? 생각하고 바로 재귀로 푼거같다!
이놈의 빡대가리를 어떻게하면 좋을까..😢😢😢😢😢😢