[Python/파이썬] 백준 16953 - A -> B

문제 설명

 

입출력 예제

 

---

풀이 코드

이 문제는 딱 보고 BFS 문제다라고 생각하진 못했지만

너비 우선 탐색 알고리즘 카테고리를 풀고 있기 때문에 BFS로 문제를 풀어 보았다.

 

1. 큐에 연산을 통해 값이 변할 a와 첫 연산 횟수 1을 튜플로 묶어 추가해준다.
2. 큐가 빌 때 까지 a의 뒤에 숫자 1을 추가한 수와 a * 2를 한 수를 추가하여 연산 횟수를 하나씩 올린다.
3. 만약 a의 수가 b보다 크면 다음 큐를 꺼내어 확인한다.
4. a와 b가 같다면 연산횟수 cnt를 출력하고 종료한다.
5. 큐가 빌때 까지 a와 b가 같지 않다면 -1을 출력한다.

아래의 사진은 a : 2 , b : 162 일 때 bfs를 통해 나온 (a, cnt) 값들이다.

처음에는 a > b 일 때 continue를 하지 않아 정답과 다른 값이 나왔는데 이 로그를 찍어보고

a > b 일 때 continue를 추가해야함을 깨닫게 되었다.

 

 

정답 코드

from collections import deque
import sys
input = sys.stdin.readline

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

def bfs(a, b):
    q = deque()
    q.append((a, 1))

    while q:
        a, cnt = q.popleft()

        if a > b:
            continue
        if a == b:
            print(cnt)
            break
            
        q.append((int(str(a) + "1"), cnt + 1))
        q.append((a * 2, cnt + 1))
    else:
        print(-1)

bfs(a, b)