백준 / 13913 / 숨바꼭질 4 / python

첫 시도

from collections import deque
Max = 100001
n, k = [int(v) for v in input().split()]

q = deque()
visited = [False] * (Max)

q.append([n])

while q:
    l = q.popleft()
    w = l[-1]
    visited[w] = True
    if w == k:
        break
    if w - 1 >= 0  and not visited[w-1]:
        visited[w-1] = True
        q.append(l+[w-1])
    if w + 1 < k+1 and not visited[w+1]:
        visited[w+1] = True
        q.append(l + [w+1])
    if w * 2 <= k + 1 and not visited[w*2]:
        visited[w*2] = True
        q.append(l + [w*2])

print(len(l)-1)
print(*l)

이 문제를 위 코드처럼 큐에 경로를 계속해서 저장해 나가는 방식으로하면 당연하게도 메모리 초과가 뜬다.

이 문제는 visited를 단순히 bfs 탐색에서 방문 여부로만 사용하지 않고 어디에서 왔는지 즉 이전 경로를 저장하는 방식으로 사용하여 해결할 수 있다.

주의할 점은 이동 경로에 0이 포함되어 있으므로 visited를 0으로 초기화 시키면 안된다는 점이다. 0으로 초기화 시키고 0으로 방문 여부를 판단하게 되면 0 지점에 대한 bfs가 계속 반복되어 메모리 초과가 발생할 수 있다.

수정 코드

from collections import deque
n, k = [int(v) for v in input().split()]

q = deque()
l = k+2 if k >= n else n
visited = [-1] * l

q.append([n,0])

while q:
    w, deph = q.popleft()
    if w == k:
        print(deph)
        result = []
        t = w
        while t != n:
            result.append(t)
            t = visited[t]
        result += [n]
        print(*result[::-1])
        break

    if w - 1 >= 0  and visited[w-1] == -1:
        visited[w-1] = w
        q.append([w-1, deph+1])
    if w + 1 < k+1 and visited[w+1] == -1:
        visited[w+1] = w
        q.append([w+1, deph+1])
    if w * 2 <= k + 1 and visited[w*2] == -1:
        visited[w*2] = w
        q.append([w*2, deph+1])

visited로 경로를 추적하는 신박한 방법을 알 수 있게해준 문제이다.