백준 16953 (bfs)

 

from collections import deque

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

q = deque([(a, 1)])

while q:
    now, cnt = q.popleft()
    if now == b:
        print(cnt)
        break
    if now * 2 <= b:
        q.append((now * 2, cnt + 1))
    if now * 10 + 1 <= b:
        q.append((now * 10 + 1, cnt + 1))
else:
    print(-1)

 

이 문제는 구현으로 풀어도 되지만 bfs로 풀이를 해보았다.

구현으로 풀 시에는 top-down방식으로 b->a 로 풀어나가야 하지만, bfs풀이로는 bottom-up 방식으로 a -> b로 풀어가면 된다.

큐에 a값과 연산횟수값(처음1)을 넣어주고 시작한다.

popleft()로 큐의 값이 있을 때 빼주어 현재값을 now에, 연산횟수를 cnt에 저장한다.

now값과 b값을 비교하며 b값과 같으면 바로 연산횟수cnt를 출력하고 종료.

아니면, now값에 2를 곱한 값 또는 뒤에 1을 붙인 값(now * 10 + 1)이 b와 같거나 작을 때 큐에 넣어준다. (cnt값 + 1)

그렇게 now값이 b값과 같아질 때까지 반복해준다.

끝난 후 값이 같아지지 않는다면, -1을 출력한다.