[BOJ] (BFS)13913번 숨바꼭질 4

최대 사이즈만큼 미리 배열을 생성한다.

반복문안에 방문한 점을 표시하기 위해 arr[next]=cnt+1   문을 추가했다.

이미 방문한 점에는 더 짧은 경로로 도달할 수 있는데, 굳이 큐에 추가할 필요가 없기 때문이다.

이렇게 방문한 점을 표시하지 않으면 큐의 길이가 기하급수적으로 늘어나 메모리 초과가 발생한다.

 

 

from collections import deque

n, k = map(int, input().split())
SIZE = 100001
arr = [0] * SIZE
arr[n] = -1
def f():
    # n==k
    if n==k:
        return 0, []
    
    # k < n
    if k < n:
        return n-k, [i for i in range(n, k-1, -1)]
    
    
    q = deque()
    q.append((n, 0, [n]))
    
    while q:
        now, cnt, route = q.popleft()

        # x+1
        next = now+1
        if next == k:
            return cnt+1, route+[next]
        
        if next < SIZE and arr[next]==0:
            q.append((next, cnt+1, route+[next]))
            arr[next] = cnt+1
        
        # x-1
        next = now-1
        if next == k:
            return cnt+1, route+[next]
        
        if next >= 0 and arr[next] == 0:
            q.append((next, cnt+1, route+[next]))
            arr[next] = cnt+1
            
        # x*2
        next = now*2
        if next == k:
            return cnt+1, route+[next]
        
        if next < SIZE and arr[next]==0:
            q.append((next, cnt+1, route+[next]))
            arr[next] = cnt+1
            
            
cnt, route = f()
print(cnt)
if len(route)==0:
    print(n)
else:
    print(*route)

 

 

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

13913번: 숨바꼭질 4