[BOJ] 백준 16953 A → B - Python3 풀이

아침에 재밌는 문제를 발견했다. 

 

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

16953번: A → B

 

bfs 문제인데 꽤나 재밌게 풀었다. 

 

아래 풀이를 첨부한다. 

 

from collections import deque

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

q = deque()
q.append((a, 1))

while q:
    curr_pos, count = q.popleft()
    if curr_pos > b:
        continue
    if curr_pos == b:
        print(count)
        break

    plus_one = int(str(curr_pos) + '1')
    mul_two = curr_pos * 2
    if plus_one <= b:
        q.append((plus_one, count + 1))
    if mul_two <= b:
        q.append((mul_two, count + 1))
else:
    print(-1)

 

재밌는 부분이 있다. while 을 돌면서 bfs 로직이 수행되는데 while 부의 바깥에 else 가 선언되어있다. 

즉 while 이 전부 돌고 나면 else 가 실행되는 것이고 그렇지 않고 중간에 break 를 하게 되면 else 가 실행되지 않고 끝나는 셈이다. 

 

이렇게 사용하는 방식을 몰랐을때는 sys.exit() 을 활용했었다. 즉 while 내에서 현재 break 가 걸리는 부분이 있을텐데 거기서 그냥 sys.exit 을 통해서 끝내버리는 방법을 썼었다. 그런데 지금 코드에서 break 와 else 를 활용하는 부분을 보면 이게 좀 더 괜찮은 코드라는 생각이 든다. 적어도 강제종료보다는 낫겠단 생각이 들었기 때문이다. 

 

이 문제를 풀면서 메모리 초과가 났는데 로직이 틀린게 아니라 한가지 실수를 해서그렇다. visited 라는 리스트를 dfs 혹은 bfs 를 풀때 습관적으로 작성해주는데 그 visited 때문에 메모리 초과가 발생한 것이다. 미리 False 로 모든 범위를 초기화해준 리스트를 만들었는데 그게 화근이었다. 

 

아마 문제에 주어지는 값의 범위가 1억이었던걸로 기억하는데 그것때문에 그렇게 메모리 초과에 걸린듯하다.