그래프는 잘 풀리나 싶더니.. 메모리 초과 (실버1)

#16953번 A -> B https://www.acmicpc.net/problem/16953

16953번: A → B

 

A 라는 수를 

1. 2를 곱한다

2. 1을 수의 오른쪽에 추가한다

 

라는 두 가지 연산을 이용해서 B라는 수로 만들 때, 연산횟수를 출력하면 된다.

 

처음에는 DP라고 생각했었는데, 알고보니 BFS였다. (아마 연산의 종류가 두 가지이기 때문이 아닐까..?)

 

틀린코드

from collections import deque

A, B = map(int, input().split())

visited = [False]*(B+1)
que = deque()
que.append(A)
visited[A] = 1
while que:
    num = que.popleft()
    if num == B:
        break
    for new_num in [num*2, int(str(num) + "1")]:
        if 0 < new_num <= B and not visited[new_num]:
            que.append(new_num)
            visited[new_num] = visited[num] + 1
            # 먼저 도달한 경우가 최소 연산 횟수일거라는 가정
print(visited[B] if visited[B] else -1)

 

잘 짰다고 생각했는데, 메모리 초과가 났다. 아무래도 입력값 B의 최대크기가 1억이다 보니, visitied의 길이가 1억이 되면서 메모리 초과가 난 듯 하다.

 

해결책을 고민했다.

근데 생각해보니, 연산의 과정에서 한번 나왔던 수가 또 나올거라는 예상이 틀렸다.

연산은 2를 곱하거나 1을 덛붙이는 형태로 진행된다.

즉 계속 증가만 하기 때문에 방문기록을 하면서 중복연산을 제외시킬 필요가 없다.

 

그냥 아주 단순한 형태의 BFS를 진행하면 된다.

단, que에 저장되는 값이 단순 node의 위치가 아니라 그 node까지 가는데 필요한 cost(비용)을 포함한 2차원 데이터 형태로 저장되어야한다.

 

정답코드

from collections import deque

A, B = map(int, input().split())

que = deque()
que.append((A, 1))
answer = -1
while que:
    num, cost = que.popleft()
    if num == B:
        answer = cost
        break
    for new_num in [num*2, int(str(num) + "1")]:
        if 0 < new_num <= B:
            que.append((new_num, cost+1))
            # 먼저 도달한 경우가 최소 연산 횟수일거라는 가정
print(answer)

 

answer 의 초깃값을 -1로 설정한 이유는 답이 나오지 않을 경우에 (B에 도달하지 못할 경우) -1을 출력해야하기 때문이다.

 

그래프를 다루는데 익숙해진건지 이 문제가 비교적 쉬운 편인건지는 잘 모르겠다.

 

실버 1이 능숙하게 풀려서 기뻤다.