백준 / 12852 / 1로 만들기 2 / python

첫 시도

from collections import deque

n = int(input())

q = deque()
q.append([n])

while q:
    t = q.popleft()
    a = t[-1]
    if a == 1:
        result = t
        break
    if a % 3 == 0:
        q.append(t + [a//3])
    if a % 2 == 0:
        q.append(t + [a//2])
    q.append(t + [a-1])

print(len(result)-1)
print(*result)

정답이 맞긴 했지만 메모리가 어마어마하게 사용되었다.

from collections import deque

n = int(input())

q = deque()
q.append([n])
visited = [False] * (n+1)

while q:
    t = q.popleft()
    a = t[-1]
    if a == 1:
        result = t
        break
    if a % 3 == 0 and not visited[a//3]:
        visited[a//3] = True
        q.append(t + [a//3])
    if a % 2 == 0 and not visited[a//2]:
        visited[a//2] = True
        q.append(t + [a//2])
    if not visited[a-1]:
        visited[a-1] = True
        q.append(t + [a-1])

print(len(result)-1)
print(*result)

방문여부를 확인하는 리스트를 만들어 불필요한 연산 제거