[백준] 16953 파이썬(python) A → B - (★)

https://www.acmicpc.net/problem/16953

16953번: A → B

 

 

메모리초과 나는 코드)

from collections import deque
a, b = map(int, input().split())
visit = [False] * (b+1)
def bfs():
    q = deque([(a, 1)])
    while q:
        now, cnt = q.popleft()
        if now == b:
            print(cnt)
            return
        for next in (2*now, now*10+1):
            if 0 <= next <= b:
                if not visit[next]:
                    visit[next] = True
                    q.append((next, cnt+1))
    print(-1)
bfs()

 

이전에 풀었던 문제랑 비슷하게 만들어 보려고 했지만 어떻게 해도 메모리 초과가 나서 포기했다.

 

정답 코드)

from collections import deque
a, b = map(int, input().split())
def bfs(a, b):
    q = deque([(a, 1)]) #1
    while q:
        now, cnt = q.popleft()
        if now == b: #2
            print(cnt)
            return
        if now*2 <= b: #3
            q.append((now*2, cnt+1))
        if now*10 + 1 <= b: #4
            q.append((now*10 + 1, cnt+1))
    print(-1) #5
bfs(a, b)

 

#1 : 데크에는 원소를 처음 삽입할때 리스트로 삽입해야해서 deque([(a, b)])로 넣는다.

#2 : bfs탈출조건

#3, 4 : 곱하기 2일때와 오른쪽 끝에 1을 더할때의 경우를 모두 bfs해준다.

#5 : 탐색에 실패했을 경우 -1출력

 

https://hgk5722.tistory.com/169

[백준] 13913 파이썬(python) : 숨바꼭질 4

 

 

1차 수정)

from collections import deque
a, b = map(int, input().split())

def bfs():
    q = deque([(a, 1)])
    while q:
        now, cnt = q.popleft()
        if now == b:
            print(cnt)
            return
        for next in (2*now, now*10+1):
            if 0 <= next <= b:
                q.append((next, cnt+1))
    print(-1)
bfs()

 

메모리초과를 일으키는 visit을 없애버리면 된다. True, False로 방문확인을 처리해서 시간을 줄이려는 visit 리스트가 오히려 이 문제에선 메모리초과로 오답처리 되는게 신기하다.