[백준][Greedy/BFS] 16953. A → B (파이썬/Python)

<BFS로 구현>

from collections import deque
a,b = map(int,input().split())
q = deque()
q.append((a,1)) # a부터 시작하는데 a부터 cnt가 1이기에 a,1을 큐에 넣어준다.

while q:
    now, cnt = q.popleft()
    #종료 조건
    if now == b:
        print(cnt)
        break
    elif now > b:
        continue
    q.append((int(str(now)+"1"),cnt+1)) # 맨오른쪽에 1을 추가해주는 것
    q.append((now*2,cnt+1)) # 2를 곱하는 것
else: #큐를 모두 돌고 비어있는 큐인데도 원하는 값이 없으면 -1 출력
    print(-1)

 

 

<Greedy로 구현>

a,b = map(int,input().split())
cnt = 1 #cnt는 1부터 시작

while b!=a:
    cnt += 1
    temp = b #b의 값에서 값을 줄여나가며 진행한다
    if b%10 == 1: #홀수인 경우
        b //= 10 #몫만 취해서 끝의 1을 사라지게 한다.
    elif b%2 == 0:#짝수인 경우
        b //= 2 #2로 나눈다(2를 원래를 곱해주는 작업이니까)

    if temp == b:
        print(-1)
        break
else:
    print(cnt)

 

✔ 개인적인 이야기 

메모리나 속도 측면에서 살펴보았을 때도 Greedy가 더 빠르게 돌아간다.

아무래도 요즘 계속 BFS DFS 문제를 풀어서 Greedy와 DP문제가 희미하다..

다시 다 골고루 풀어야겠다...