나중에 다시 풀어볼 것

• 중요 내용
  • 1차원 배열의 BFS의 경우,
    • 동빈나가 알려준대로 메모이제이션 해도 되지만
    • 메모리 초과 error가 발생할 수 있음
  • 이 문제 솔루션처럼
    • [계산한 값, cnt] 묶어서 진행해
    • 다음 진행 시 [다음 계산한 값, cnt += 1]
    • 이 문제의 경우엔 앞으로 나아가는 (오른쪽으로만 가는) 경우였긴 했음
  • 나중에 다시 풀어보고 든 생각
    - 결국 BFS가 아니라 이 유형은 queue 활용 문제인거 아님?

---

• 링크 : https://www.acmicpc.net/problem/16953
  
  

---

메모한 것

• 이거 BFS - 최단경로???

• 가능한 연산

  • A * 2
  • str(A) + '1'

• 출력물 : A를 B로 만드는 최소 연산 횟수 + 1

• 만들 수 없으면 -1

• 이거 어떤 비슷한 유형 있던거같은데 백준에 얼마전에 풀어본거중에

• 아 근데 횟수니까 [[0] * 100] 이런거 하나 만들어놓고

• 연산한 값이 index가 되는거고(이게 중요), 연산한 값을 방문할 때마다 += 1해주면서

• 최소 수니까 이동중에(= if index == B)가 되면 바로 print()하고 exit(0) 하면 될듯?

---

1차적으로 접근해서 푼 - 메모리 초과..

• 동빈나에서 알려준 메모이제이션 기법(?)을 활용해서 1차원 BFS를 진행한건데...

''' 내가 푼 - 1차원 벡터의 BFS 최단거리 유형인듯 '''
from collections import deque

def bfs(a, b, visit):
    que = deque([a])
    visit[a] = 1
    
    while que:
        now = que.popleft()
            
        # bfs 이므로 두 가지 케이스 다 수행하여 queue에 push
        if now * 2 <= b: 
            after1 = now * 2
            visit[after1] = visit[now] + 1
            que.append(after1)
            if after1 == b:
                return visit[after1]
            
        if int(str(now) + '1') <= b:
            after2 = int(str(now) + '1')
            visit[after2] = visit[now] + 1
            que.append(after2)
            if after2 == b:
                return visit[after2]

a, b = map(int, input().split())
visit = [0] * (b + 1)                     # 인덱스 0부터 시작이므로

answer = bfs(a, b, visit)
print(answer) if answer else -1

---

메모리 초과 문제 해결해야 한다

• 참고 블로그 링크 : https://my-coding-notes.tistory.com/210

''' 블로그 해답 1 - BFS 활용 '''

from collections import deque

a, b = map(int, input().split())
que = deque()
que.append((a, 0))              # (중요) 시작값과 count 횟수를 묶어서 넣어준다

while que:
    now, cnt = que.popleft()
    
    if b < now:                # now가 초과할 경우
        continue
    if b == now:               # 처음으로 찾는 순간에 바로 끝
        print(cnt+1)           # +1 더한값을 출력하라 함
        break
        
    # bfs니까 둘 다 넣어줌
    que.append((now * 2, cnt + 1))
    que.append((int(str(now) + '1'), cnt + 1))
    
else:
    print(-1)                 # (매우 중요) 무한루프 빠져나오는 방법 : while-else 문

---

2주 후 다시 풀어봄 - 나중에 또 풀어보자

• 처음에 접근 못했다가, 추가 배열(graph, arr 등) 안쓰는 유형인 것만 확인하고 다시 해서 풀었음
• 1차원 배열 BFS는 이렇게 Deque만 사용하고, graph[] 사용X일 수 있음!!

from collections import deque

a, b = map(int,input().split())
que = deque()                   # (중요) "괄호"로 넣어줘야한다!!!
que.append((a, 0))              # (중요) 시작값과 count 횟수를 묶어서 넣어준다
ans = 0

while que:
    x, cnt = que.popleft()
    
    if x == b:
        ans = cnt
        break
        
    for nx in [x*2, int(str(x)+'1')]:
        if 0 <= nx <= b:            
            que.append((nx, cnt+1))
        
print(ans+1) if ans > 0 else print(-1)