[BOJ] 숨바꼭질

from collections import deque
def bfs(num):
    q.append((num, 0))
    check.add(num)
    while len(q) != 0:
        n, cnt = q.popleft()
        if n == M:
            ans = cnt
            break
        for i in range(3):
            if i == 0:
                if n+1 not in check and n+1 <= 100000:
                    check.add(n+1)
                    q.append((n+1, cnt+1))
            elif i == 1:
                if n-1 not in check and n-1 <= 100000:
                    check.add(n-1)
                    q.append((n-1, cnt+1))
            elif i == 2:
                if n*2 not in check and n*2 <= 100000:
                    check.add(n*2)
                    q.append((n*2, cnt+1))
    return ans


N, M = map(int, input().split())
check = set()
q = deque()
result = bfs(N)
print(result)

문제 풀이

처음에 중복 체크를 visited [0] * 100000 이렇게 했었는데, 메모리 초과가 발생한다. 또한 deque를 써야 시간초과 없이 통과할 수 있었던 것 같다. 시간초과랑 메모리 초과때문에 시간 걸렸던 문제...