1697번. 숨바꼭질(Python, BFS, 메모리초과)

문제
(https://www.acmicpc.net/problem/1697)

풀이

수빈이는 x-1, x+1, 혹은 2*x로 이동할 수 있다. 완전 탐색으로 답을 찾아가지만, 이미 방문했던 위치는 다시 탐색할 필요가 없으므로, 방문한 위치를 저장하는 배열이 필요하다. 또한, 최단 시간을 저장해야하므로 queue에 위치와 시간을 담은 튜플을 저장하였다.

구현

from collections import deque

n, k = map(int, input().split())

visited = set()
queue = deque()
queue.append((n,0))
visited.add(n)

while queue:
    popNum,timeCnt = queue.popleft()
    if popNum == k : break
    for i in range(3):
        if i == 0: nx = popNum + 1
        if i == 1: nx = popNum - 1
        if i == 2: nx = 2 * popNum
        if nx in visited : continue
        queue.append((nx,timeCnt+1))
        visited.add(nx)

print(timeCnt)

실패

하지만 메모리 초과가 났다. 그 이유는 n과 k가 100,000까지 될 수 있는데, queue에 100,000이 넘는 수와 0보다 작은 수까지 저장하기 때문이다. 어차피 100,000과 음수는 담을 필요가 없으므로 조건문에서 visited에 존재하는지 여부뿐만이 아니라, 100,000이넘는지도 그리고 음수인지 확인하도록 하자.

최종 구현

from collections import deque

n, k = map(int, input().split())

visited = set()
queue = deque()
queue.append((n,0))
visited.add(n)

while queue:
    popNum,timeCnt = queue.popleft()
    if popNum == k : break
    for i in range(3):
        if i == 0: nx = popNum + 1
        if i == 1: nx = popNum - 1
        if i == 2: nx = 2 * popNum
        if nx in visited or nx<0 or nx > 100000 : continue
        queue.append((nx,timeCnt+1))
        visited.add(nx)

print(timeCnt)