[백준16953] / A → B - 그래프(BFS)

 

백준16953

 

푼 날짜 : 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로 시작했다.