백준 16953 A -> B Python 그래프 BFS 실버2

실수 한 점:

1. 10의 9승까지 값을 받을 수 있기 때문에, 일반적인 bfs 풀이를 사용할 경우 메모리 오류가 뜬다.

2. 부분집합을 이용한 DFS 풀이처럼 문제를 풀이할 수 있다면 풀 수 있음을 인지했음, 하지만 이를 활용할 방법을 유연하게 생각하지 못함,

=> 인자로 cnt를 받아서 활용했으면 바로 풀이가 가능한 단계까지 풀이했었음

 

메모리 초과 풀이 

from collections import deque
def bfs(n,m):
    Q = deque()
    Q.append(n)
    visited[n] = 1
    while Q:
        v = Q.popleft()
        if v > m: continue
        if v==m:
            return visited[m]
        for w in [v*2,int(str(v)+'1')]:
            if 0< w <= m:# 백만 이하의 자연수
                if visited[w] ==0:
                    visited[w] = visited[v] + 1
                    Q.append(w)
    return -1

N,M = map(int,input().split())
visited = [0] * (M + 1)
print(bfs(N,M))

정답 풀이

from collections import deque

def bfs(n,m):
    Q = deque()
    Q.append((n,1))
    while Q:
        v,cnt = Q.popleft()
        if v > m: continue
        if v==m:
            return cnt
        Q.append((v*2, cnt + 1))
        Q.append((v*10 + 1, cnt + 1))
    return -1

N,M = map(int,input().split())
print(bfs(N,M))