푼 날짜 : 2024.08.17
푼 문제 : [16953] / A → B
사용한 언어 : python
푼 방법 :
너비 우선 탐색으로 접근하였다.
처음 풀었을 때 메모리 초과가 났다.
아무래도 범위가 최대 10^9 이기 때문에 배열을 다 만든다고 하면...
그래서 생각한 방법이 dictionary다.
불필요한 visited를 다 만들어 놓지 말고 필요한 값만 저장하기로 했다.
사실 리스트에서 딕셔너리로 변경한 것 말고는 크게 BFS문제를 벗어날 정도의 난이도가 아니었기 때문에 코드는 전반적으로 비슷하다.
코드 :
import sys
from collections import deque
A, B = map(int, sys.stdin.readline().split())
visited = {} # 딕셔너리로 만들기
px = ['*', '+']
def BFS(visited, v):
queue = deque([v])
visited[v] = 1
while queue:
now = queue.popleft()
nx = now
if nx == B:break
for i in px:
if i == '*': nx = now * 2
elif i == '+': nx = int(now*10+1)
if 0<nx<=B and nx not in visited:
queue.append(nx)
visited[nx] = visited[now] + 1
BFS(visited, A)
print(visited[B] if B in visited else -1)
아 그리고 또 한가지는,
필요한 연산의 최솟값에 1을 더한 값을 출력
이라는 조건이 있었기 때문에 visited를 처음에 1로 시작했다.
