[백준] 25418 - 정수 a를 k로 만들기

25418번: 정수 a를 k로 만들기

✏️  풀이

입력으로 a, k가 주어지는데 그냥 a를 k로 만드는 최소 연산 횟수를 출력하는 것이다. 최소, 최단 이런 단어가 보이면 이제는 바로 BFS로 풀면 되겠다는 생각을 한다. 뭐 아닐 수 도 있겠지만, 그건 많이 풀어보면 BFS구나, 아니구나를 판단할 수 있을 것이라고 믿는다. 

 

큐에는 시작과 연산 횟수를 넣었다. 그렇게 연산을 하면 cnt를 증가 시키고, k에 도달하면 출력을 하고 끝을 낸다. BFS의 개념만 알면 금방 풀 수 있는 문제라서 쉽게 풀 수 있었다.

💻  코드

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

start, dest = map(int, input().split())
q = deque([(start, 0)])
visited = set([start])
while q:
    cur, cnt = q.popleft()
    if cur == dest:
        print(cnt)
        break
    cnt += 1
    if cur*2 <= dest and cur*2 not in visited:
        q.append((cur*2, cnt))
        visited.add(cur*2)
    if cur+1 <= dest and cur+1 not in visited:
        q.append((cur+1, cnt))
        visited.add(cur+1)