[백준][python] 16953 A->B - Greedy

• 백준 16953 A -> B Silver I
• 문제링크 

16953번: A → B

나의 코드

BFS 키워드를 보고 바로 BFS로 구현했다. 주어진 테스트케이스는 통과했지만 제출했더니 시간초과가 났다.. BFS에서 방향을 정의해주는 것 대신 가능한 두 가지의 연산된 값에 대한 연산을 반복하는 식이다. 

# 시간초과 코드
import sys

def bfs(num, B):
    q = []
    q.append((num, 0))

    while q:
        newnum, count = q.pop(0)
        calcnums = [(lambda x: x * 2)(newnum), int((lambda x: x + '1')(str(newnum)))]
        for i in calcnums:
            if i > B:
                break
            elif i not in visited:
                visited.append(i)
                q.append((i, count + 1))
                if i == B:
                    return (count + 2)
    
    return -1

A, B = map(int, sys.stdin.readline().split())
visited = []
print(bfs(A, B))

 

B에서 반복적으로 연산을 수행하여 A에 도달 가능한지 계산하는 코드다. 예외처리만 세심하게 해주면 쉽게 풀리는 문제다. 생각해보니 그리디 알고리즘을 사용하는 문제였기 때문에 구현자체보다는 효율성에 좀 더 집중하면서 풀었어야 하는데.. 문제를 잘 읽어보고 여러 접근 방법을 생각해보고 푸는 습관을 길러야한다...!

a, b = map(int, input().split())
result = 1
while True:

    if a == b:
        break

    elif (b % 2 != 0 and b % 10 != 1) or (b < a):
        result = -1 # -1 출력
        break
    
    else:
        if b % 10 == 1:
            b = b // 10
            result += 1
       
        else:
            b = b // 2
            result += 1

print(result)