[백준] 16952번: A → B - Python

https://www.acmicpc.net/problem/16953

뭐 사실 재미있는 문제인가? 라고 했을 때

재미있다고 하기는 어렵구 이런 것도 그래프로 풀 수 있다는 걸 깨달아서,

문제가 안풀리면 사실 문제 분류를 보는데 

이 문제는 문제 분류를 보고 '이게 왜 이렇게 분류되어있지? 라는 생각이 들었다. 

예전 생각은 '거꾸로 계산해서 넘어오면 되는거 아닌가?'라는 생각을 했었다.

그러니까 예시로 보여주면

'''
입력값1 : 2 162 

162 : 끝이 1이 아니기 때문에 무조건 // 2
81 : 끝이 1이니까 1을 때버림
8 : 끝이 1이 아니기 때문에 무조건 // 2
4 : 끝이 1이 아니기 때문에 무조건 // 2
2 : 완성 => 만들 수 있음 

입력값2 : 4 42

42 : 끝이 1이 아니기 때문에 무조건 // 2
21 : 끝이 1이니까 1을 땜
2 : 만들 수 없음 

'''

지금 생각하니까 막상 구현 가능 할 것 같네

구현을 했는데, 30%에서 실패가 계속 나왔던 거 같다.

그래서 며칠 두다가 다시 풀었는데

얼마 전에 알고리즘 강의를 듣다가, 강사분이

엄청나게 성능 좋은 뇌가 있는데 그냥 다 계산시키면 되는거 아닌가요?
왜 컴퓨터를 배려하세요?

라는 이야기를 하셨던게 기억이 나서 걍 다 계산하면 안됨? 이라는 생각에

다시 문제를 보니, 아 그렇게 어렵지 않은 문제구나.. 하고 간단하게 구현해버렸다.

import sys
from collections import deque


def bfs(start_number, target_number):
    queue = deque()
    queue.append((start_number, 1))
    while queue:
        num, cnt = queue.popleft()
        mul_two, plus_one = num * 2, int(str(num) + '1')
        if mul_two == target_number or plus_one == target_number:
            return cnt + 1
        else:
            if mul_two < target_number:
                queue.append((mul_two, cnt + 1))

            if plus_one < target_number:
                queue.append((plus_one, cnt + 1))


a, b = map(int, sys.stdin.readline().split())
result = bfs(a,b)
if result is None:
    print(-1)
else:
    print(result)