[실버 3] 백준 25418 - 정수 a를 k로 만들기 (파이썬)

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

풀이

이 문제는 정수 A에서 출발해서 두가지 연산이 가능하다.

1. 1을 더하기 (x → x + 1)
2. 2배 만들기 (x → 2x)

를 사용하여 목표 정수 K를 만드는 최소 연산 횟수를 묻는다.

1. 그래프 모델링
   • 각 정수 i를 노드로 보고,
   • i → i+1, i → 2*i 두 개의 간선을 가진다.
   • 시작 노드는 A, 목표 노드는 K가 된다.
2. 최단 경로 탐색
   • 모든 간선의 가중치가 1이므로, 너비 우선 탐색(BFS)을 사용하면 시작점에서 목표점까지의 최소 간선 수(연산 횟수)를 구할 수 있다.
3. 구현 세부사항
   • visit[i]: 정수 i에 한 번이라도 도달했는지 표시
   • dist[i]: 시작 정수 A에서 i에 도달하기까지의 최소 연산 횟수
   • queue: BFS용 덱(Deque)
   • 인접 리스트 adj[i]를 미리 만들어 두었지만, 노드 수(K+1)가 크지 않다면 매번 두 연산을 직접 체크해도 무방하다.

queue.append(A)
visit[A] = True
dist[A] = 0

while queue:
    u = queue.popleft()
    for v in adj[u]:      # v는 u+1 또는 2*u
        if not visit[v]:
            visit[v] = True
            dist[v] = dist[u] + 1
            queue.append(v)

BFS를 진행하며, 위 코드가 작동하면 dist[k]에 최소 연산 횟수가 저장된다.

코드

# 백준 25418 - 정수 a를 k로 만들기
# 분류 : BFS

from collections import deque
A, K = map(int, input().split())

adj = [[] for _ in range(K + 1)]
for i in range(1, K + 1) :
    if i + 1 <= K :
        adj[i].append(i + 1)
    if 2 * i <= K :
        adj[i].append(2 * i)

visit = [False] * (K + 1)
dist = [-1] * (K + 1)
queue = deque()

queue.append(A)
visit[A] = True
dist[A] = 0

while len(queue) != 0 :
    u = queue.popleft()

    for v in adj[u] :
        if not visit[v] :
            queue.append(v)
            visit[v] = True
            dist[v] = dist[u] + 1

print(dist[K])