[탐색/BFS] 백준 16953 A → B - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

16953번: A → B

 

 

 

2. 문제 풀이

1) A*2
2) A*10 +1

 2가지 연산을 최소로 사용해서 A를 B로 만드는 문제입니다.

 

2022.03.19 - [Algorithm] - [탐색/BFS] 백준 9019 DSLR - 파이썬(Python)

 BFS 탐색문제로, DSLR 문제와 비슷합니다. B를 넘어서기 전까지 2가지 연산을 수행하다가 B가 되면 탐색을 종료합니다. 만약 모든 경우의 수를 탐색했는 데도 B가 되지 않는다면 -1를 출력합니다.

 

 

 

3. 코드

from collections import deque

# 입력
A, B = map(int, input().split())

# BFS 탐색
queue = deque([(1, A)])
while queue:
    cnt, x = queue.popleft()

    # B와 같다면 탐색종료
    if x == B:
        print(cnt)
        break

    # 2를 곱한다
    if x * 2 <= B:
        queue.append((cnt+1, x*2))

    # 1를 오른쪽에 추가한다
    if x * 10 + 1 <= B:
        queue.append((cnt+1, x*10+1))

# 찾지 못했다면 -1 출력
else:
    print(-1)

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 BFS 탐색에 대한 설명과 코드는 위 링크에서 보실 수 있습니다.