[백준/Python] 13549 숨바꼭질 3

문제는 여기

코드

from collections import deque
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
MAX = 100001
visited = [False] * MAX

def bfs(point):
    queue = deque()
    queue.append((point, 0))
    visited[point] = True

    while queue:
        n, time = queue.popleft()

        if n == k:
            return time
        else:
            if 0 <= 2*n < MAX and not visited[n*2]:
                queue.append((n*2, time))
                visited[n*2] = True
            if 0 <= n - 1 < MAX and not visited[n-1]:
                queue.append((n-1, time + 1))
                visited[n-1] = True
            if 0 <= n + 1 < MAX and not visited[n+1]:
                queue.append((n + 1, time + 1))
                visited[n+1] = True

print(bfs(n))

기록할 점

1. 메모리 초과
   +1, -1, *2 인 경우 bfs 해주다보면 같은 숫자가 반복되는데
   방문 처리를 안해주고 매번 계산해줘서 메모리 초과가 발생했다.

   visited = [False] * 100001 코드 추가

2. 범위를 잘못써서 틀림

   if 0 <= 2*n <= k and not visited[n*2]:

   이런식으로 ..

   수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 

   에서 알 수 있듯이 이동 가능 범위는 k가 아니라 100001까지이다.
   문제를 잘 읽는 건 아주 중요하다