[Python] 25418번 정수 a를 k로 만들기

✏️ 문제

 

문제 파악

최소 연산 횟수를 구하므로 BFS를 사용해서 풀어야 한다.

 

문제에서 연산 종류가 2가지 있다.

• a + 1
• a * 2

이를 바탕으로 다음과 같이 코드를 짜면 next_v에 v + 1, v * 2 가 차례대로 들어가게 된다.

for next_v in (v+1, 2*v):

 

제출했는데 IndexError가 계속 떠서 애초에 if 조건문에 next_v <= k 라는 조건을 주어 에러가 안뜨게 index를 넘지 않도록 하였다.

 

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 다이나믹 프로그래밍

 

 

코드

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

a, k = map(int, input().split())
graph = [0] * (k + 1)

def bfs(v):
  q = deque([v])
  graph[v] = 0

  while q:
    v = q.popleft()

    if v == k:
      break

    for next_v in (v+1, 2*v):
      if next_v <= k and graph[next_v] == 0:
        graph[next_v] = graph[v] + 1
        q.append(next_v)

bfs(a)
print(graph[k])

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS