[백준/Python] 13913 숨바꼭질 4

문제는 여기

코드

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

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

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

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

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

result = bfs(n)
print(result)

ans = []
temp = k
ans.append(k)

for i in range(result):
    ans.append(moving[temp])
    temp = moving[temp]
print(' '.join(map(str, ans[::-1])))

기록할 점

며칠 전 숨바꼭질 3을 풀었던터라 경로를 출력하는 부분에 있어서만 기록해보겠슴

첫 번째 시도는

a[17] = [5,10,9,18,17]

이런식으로 값을 전부 가지고 있는 평범한 방식을 생각해냈는데
메모리 초과로 실패했다

지당하신 말씀. 이러니 안되지요
감사합니다 꾸벅

두 번째 시도
방문했을 때 바로 직전의 값만 가지고 있기로 했다
출력할 때는 역추적해서 출력하는 걸로 !

ans = []
temp = k
ans.append(k)

for i in range(result):
    ans.append(moving[temp])
    temp = moving[temp]
print(' '.join(map(str, ans[::-1])))