[Python] 16953번 A → B

✏️ 문제

 

문제 파악

연산의 최솟값을 구해야 하므로 BFS를 사용해서 풀어야한다.

이 문제에서 배열로 풀게 되면 A와 B의 범위가 매우 커서 배열 초기화시 메모리 초과가 뜨게 된다.

그래서 배열 대신 딕셔너리 { } 를 사용하면 필요한 노드에 대해서만 메모리를 할당하여 메모리 사용량을 줄일 수 있다!

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 그리디 알고리즘

 

 

코드

from collections import deque

a, b = map(int, input().split())
graph = {}

def bfs(v):
    q = deque([v])
    graph[v] = 0
    
    while q:
        node = q.popleft()

        if node == b:
            return graph[node] + 1 

        for next_node in (2*node, int(str(node)+'1')):
            if next_node <= b and next_node not in graph: 
            # next_node가 graph에 존재하지 않는다면 = next_node를 아직 방문하지 않았다면
                graph[next_node] = graph[node] + 1
                q.append(next_node)
  
    return -1 

print(bfs(a))

 

 

 

---

 

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

[알고리즘] DFS와 BFS