[백준] 16953 A→B (python)

BFS 풀이 1 - count 0에서 시작하는 경우 (96ms)

from collections import deque

a, b = map(int,input().split())

def bfs(start, count):
    queue = deque([(a, 0)])

    while queue:
        now, count = queue.popleft()
        if now == b:
            print(count+1)
            return
        if now * 2 <= b:
            queue.append((now*2, count+1))
        if now * 10 + 1 <= b:
            queue.append((now*10+1, count+1))
    print(-1)

bfs(a,b)

BFS 풀이 2 - count 1에서 시작하는 경우 (76ms)

from collections import deque

a, b = map(int,input().split())

def bfs(start, count):
    queue = deque([(a, 1)])

    while queue:
        now, count = queue.popleft()
        if now == b:
            print(count)
            return
        if now * 2 <= b:
            queue.append((now*2, count+1))
        if now * 10 + 1 <= b:
            queue.append((now*10+1, count+1))
    print(-1)

bfs(a,b)

알게된 것 : import sys를 사용한다고 항상 좋은 것은 아님!

• Chat GPT가 알려주는 문제의 이유는 아래와 같음
  • 모듈 로딩 시간:
    • Python에서 모듈을 import할 때, 해당 모듈을 메모리에 로드하고 초기화하는 과정이 필요합니다. sys 모듈은 Python의 기본 라이브러리 중 하나이므로 일반적으로 로딩 시간이 짧지만, 여전히 어느 정도의 시간이 소요됩니다.
  • 경로 탐색:
    • import 문을 사용할 때, Python 인터프리터는 모듈을 찾기 위해 sys.path에 지정된 디렉터리들을 탐색합니다. 이 과정에서 파일 시스템 접근이 발생하며, 특히 경로에 많은 디렉터리가 포함되어 있거나 파일 시스템이 느린 경우 시간이 더 걸릴 수 있습니다.
  • 초기화 작업:
    • 모듈을 import할 때, 해당 모듈의 초기화 코드가 실행됩니다. sys 모듈은 비교적 간단하지만, 초기화 작업에서 시스템 정보나 환경 변수를 읽어들이는 과정에서 시간이 소요될 수 있습니다.
  • 캐싱 및 컴파일:
    • 모듈을 처음 import할 때, Python은 모듈을 컴파일하여 .pyc 파일을 생성하고 이를 캐싱합니다. 이후에는 캐시된 .pyc 파일을 사용하여 import 속도를 높이지만, 처음 import할 때는 이 과정이 필요하므로 시간이 더 걸릴 수 있습니다.

# BFS를 사용하지 않은 다른 풀이 보기

n,m = map(int,input().split())
count=0
while n!=m:
    if n>m:
        count=-2
        break
    elif str(m)[-1]=='1':
        m=m//10
        count+=1
    elif m%2==0:
        m=m//2
        count+=1
    else:
        count=-2
        break
print(count+1)

• 이 방식으로 푸는게 시간, 메모리, 코드 길이 모든 면에서 이득이다!