[Python] 백준 16953 A -> B | 그리디 알고리즘 | BFS

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

16953번: A → B

 

 

문제 해결 포인트

- 그리디 알고리즘, BFS

- 입력 값에 대해서 두개의 연산을 연쇄적으로 수행함으로 모든 경우의 수 확인

- 원하는 값이 발견되면 출력 후 즉시 종료( 가장 먼저 발견되는 연산 횟수가 가장 작은 연산이므로) : 그리디

- 연산 값이 타켓 값보다 크다면 해당 서브 트리에 대해서 더이상 탐색하지 않도록 한다.

 

 

작성 코드

from collections import deque
a, b = map(int, input().split())
que = deque()  # BFS

que.append((a*2, 2))  # 2곱하기 연산
que.append((int(str(a)+'1'), 2))  # 1자리수 더하기 연산

while que:  # 큐에 값이 있을 동안
    q = que.popleft()
    if q[0] == b:
        print(q[1])  # 가장 먼저 발견 되는 타겟값 연산 횟수 출력
        exit()  # 종료
    else:
        # 두 개의 연산에 대해 타겟 값보다 작거나 같다면 큐에 삽입
        if q[0]*2 <= b:
            que.append((q[0]*2, q[1]+1))
        if int(str(q[0])+'1') <= b:
            que.append((int(str(q[0])+'1'), q[1]+1))

print(-1)  # 모든 경우의 수에서 타겟 찾지 못 한다면

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚