백준 16953 A → B (Python)

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

16953번: A → B

아무리 생각해도 이 문제는 그리디보다는 BFS에 가깝다고 생각을 한다.

 

중복이 있으면 반복이 오래걸리고 같은 계산을 반복하기에 set으로 만들어서 중복을 제거하도록 했다.

 

우선 첫 수를 집합에 넣는다.

그리고 반복문을 실행하는 데, 조건은 B가 집합에 없고 집합이 비어있지 않는다는 조건이다.

반복문이 실행할 때마다, 임시로 저장할 집합을 만들고 해당 집합에 전역 집합에 있는 수에 *2, *10 + 1 한 값을 다 넣어두고 해당 집합을 전역 집합으로 바꿔준다.그리고 반복문이 실행될 때마다 결과값을 +1 해준다.

 

출력에서는 B가 발견이 되어 집합에 수가 남아있다면 result를 출력하고, 아니라면 B를 찾지 못하기 때문에 -1을 출력해준다.

import sys

A, B = map(int, sys.stdin.readline().split())

greedy = set()
greedy.add(A)

result = 1

while B not in greedy and greedy:

    current_greedy = set()

    while greedy:
        element = greedy.pop()
        if element * 2 <= 10 ** 9:
            current_greedy.add(element * 2)
        if element * 10 + 1 <= 10 ** 9:
            current_greedy.add(element * 10 + 1)

    result += 1
    greedy = current_greedy


print(result if greedy else -1)