1697번: 숨바꼭질 (acmicpc.net)

##
BFS문제

##
import collections
N,K = map(int,input().split())

q = collections.deque()
q.append(N)
visited = set()
visited.add(N)

count = 0
while(True):
    q2 = collections.deque()

    if K in q:
        break
   
    while(len(q) != 0):
        n = q.pop()
        for tmp in (n+1,n-1,n*2):
            if (tmp not in visited) and (0<= tmp <= 100000):
                q2.append(tmp)
                visited.add(tmp)
    count += 1
    q = q2
   
print(count)
성공한 코드


import collections
N,K = map(int,input().split())

q = collections.deque()
q.append(N)
visited = set()
visited.add(N)

count = 0
while(True):
    q2 = collections.deque()
   
    while(len(q) != 0):
        n = q.pop()
        if n+1 not in visited:
            q2.append(n+1)
            visited.add(n+1)
        if n-1 not in visited:
            q2.append(n-1)
            visited.add(n-1)
        if (n*2 not in visited) and (n*2 < K):
            q2.append(n*2)
            visited.add(n*2)
    count += 1
    q = q2
    if K in q:
        break
print(count)
이렇게 할 경우 음수값이 많이 들어가게 된다.
K를 크게하고 deque를 출력하면서 보면 알수 있다.
정답으로 낸 코드도 숫자가 많이 들어가서 잘 판단이 안되긴 했는데

처음에 메모리 초과가 뜨면 값이 많이 저장되는게 문제라는건 바로 알수있는데, 어떤식으로 걸러내야되는지 잘 감이 잡히지 않았다. 그냥 이런식으로 문제 조건 이용해서 먼저 걸러내면 좋을듯

어쨌든 BFS 문제로 이미 체크한 숫자는 다시 체크하지 않도록 하면서 찾아내면 된다.
범위를 제한하지 않아도 컴퓨터로 돌리면 정답은 나오지만
코드 제출시 메모리가 초과된다. 이것만 주의하면 되는것으로 보임