BOJ_12852_1로 만들기 2_java

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 백준 12852 1로 만들기 2
 실버 1
 */
public class BOJ_12852_1로만들기2 {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        Num ans = bfs();
        Collections.reverse(ans.history);
        System.out.println(ans.cnt);
        for (int i : ans.history){
            System.out.print(i + " ");
        }
    }

    public static Num bfs(){
        boolean[] visited = new boolean[N+1];
        Queue<Num> queue = new LinkedList<>();
        queue.offer(new Num(1, 0, new ArrayList<>()));
        while (true){
            Num now = queue.poll();

            if(now.X == N){ // N에 도달하는 경우
                return now;
            }

            if (visited[now.X]) continue; // 이미 방문했던 경로
            visited[now.X] = true;

            if(now.X * 3 <= N){
                List<Integer> tmp1 = new ArrayList<>();
                tmp1.addAll(now.history);
                queue.offer(new Num(now.X*3, now.cnt+1, tmp1));
            }
            if(now.X * 2 <= N){
                List<Integer> tmp2 = new ArrayList<>();
                tmp2.addAll(now.history);
                queue.offer(new Num(now.X*2, now.cnt+1, tmp2));
            }
            if(now.X + 1 <= N){
                List<Integer> tmp3 = new ArrayList<>();
                tmp3.addAll(now.history);
                queue.offer(new Num(now.X+1, now.cnt+1, tmp3));
            }
        }

    }

    public static class Num{
        int X;
        int cnt;
        List<Integer> history;
        public Num(int X, int cnt, List<Integer> history){
            this.X = X;
            this.cnt = cnt;
            this.history = new ArrayList<>();
            this.history.addAll(history);
            this.history.add(X);
        }

        @Override
        public String toString() {
            return this.X + " " + this.cnt + " \n" + this.history;
        }
    }

}