[백준]25418번: 정수 a를 k로 만들기 (파이썬)

📌 문제 탐색하기

 A와 K가 주어지면, (A + 1), (2 * A) 두 종류의 연산을 통해 A를 K로 만들기 위한 최소 연산의 횟수를 출력해야한다.

🔎  시간 복잡도

• 1 ≤ A < K ≤ 1,000,000 숫자 내에서 BFS를 사용해 최단 경로를 찾으므로 시간복잡도는 O(N)이다.

🔎 접근 방법 및 알고리즘

새로운 숫자를 방문할 때 그 숫자까지의 최소 연산 횟수를 기록하고 새로운 숫자를 큐에 추가해야한다. 

📌 코드 설계하기

1. A와 K를 입력받는다.

2. 데큐를 사용해서 큐를 만든다.

3. 딕셔너리 V는 각 숫자까지의 최소 연산 횟수를 저장한다

4. BFS탐색: 만약 현재 숫자 C가 K라면, 탐색을 종료한다. 

5. v[x] = v[c] + 1 # 연산 횟수 기록

6. q += [x] # 큐에 새로운 숫자 추가

📌 시도 회차 수정사항

📌 정답 코드 

from collections import deque
a,k=map(int,input().split())
q=deque([a])
v={a:0}

while q:
    c=q.popleft()
    if c==k: break
    for x in [2*c,c+1]:
        if x in v or x>k: continue
        v[x]=v[c]+1
        q+=[x]
        
print(v[k])