BOJ - 12852

백준 문제 링크
1로 만들기 2

❓접근법

1. BFS를 사용했다.
2. 이번에는 좀 특이하게 큐에 (n, [n])을 넣어준다.
   뒤에 있는 리스트에는 방법에 포함되어 있는 수를 넣을 계획이다.
3. 큐가 비어있을 때까지,
   num, ans = queue.popleft() 로 원소를 가져온다.

• 만약 num이 1과 같다면
  print(len(ans) - 1)
  print(*ans)
• 만약 아직 방문하지 않았다면 visited[num]을 방문처리해준다.
  또한, 가능한 연산 3가지는 다음과 같다.

if not visited[num]:
	visited[num] = True
    if num % 3 == 0:
    	queue.append((num // 3, ans + [num // 3]))
    if num % 2 == 0:
        queue.append((num // 2, ans + [num // 2]))
    queue.append((num - 1, ans + [num - 1]))

👌🏻코드

from collections import deque

n = int(input())

queue = deque()
queue.append((n, [n]))

visited = [False] * (n + 1)

while queue:
    
    num, ans = queue.popleft()
    
    if num == 1:
        print(len(ans) - 1)
        print(*ans)
        break
        
    if not visited[num]:
        visited[num] = True
        
        if num % 3 == 0:
            queue.append((num // 3, ans + [num // 3]))
        if num % 2 == 0:
            queue.append((num // 2, ans + [num // 2]))
            
        queue.append((num - 1, ans + [num - 1]))