백준|12852번|1로 만들기 2

문제설명
정수 X에 3으로 나누기, 2로 나누기, 1을 빼기 총 3가지의 연산을 사용하여 1로 만드는 데 필요한 최소한의 연산횟수와 연산과정을 출력하는 문제입니다.

작동 순서
1. 정수 X를 입력받습니다.
2. 정수 X를 연산할수 있는 경우 연산을 수행하고 연산횟수를 현재 연산횟수+1로 대입한 뒤 정수 X에서 연산을 한 숫자의 출처로 정수 X룰 남깁니다.
3. 1을 만드는데 필요한 연산의 횟수를 출력합니다.
4. 1부터 시작해서 출처를 찾아가며 출력합니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class 백준_12852번_1로만들기2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] dp = new int[1000001][2];
        int num;
        Queue<Integer> q = new LinkedList<>();
        q.add(N);
        dp[N][0]=1;
        while(!q.isEmpty()){
             num = q.poll();

             if(num-1>0) {
                 if (dp[num - 1][0] == 0) {
                     q.add(num - 1);
                     dp[num - 1][0] = dp[num][0] + 1;
                     dp[num-1][1]=num;
                 }
             }

             if(num%3==0){
                 if(dp[num/3][0]==0) {
                     q.add(num / 3);
                     dp[num/3][0] = dp[num][0] + 1;
                     dp[num/3][1] = num;
                 }
             }

             if(num%2==0){
                 if(dp[num/2][0]==0){
                     q.add(num/2);
                     dp[num/2][0]=dp[num][0]+1;
                     dp[num/2][1]=num;
                 }
             }
        }
        System.out.println(dp[1][0]-1);

        int pointer = 1;
        int[] route = new int[dp[1][0]];
        for(int i=0;i<dp[1][0];i++){
            route[i]=pointer;
            if(pointer==N) break;
            pointer = dp[pointer][1];
        }
        for(int i=dp[1][0]-1;i>-1;i--) System.out.print(route[i]+" ");
    }
}

후기
다른 분들의 풀이들과 비교를 해보니 제가 작성한 코드는 너무 비효율적인 코드인것 같습니다. 꾸준히 공부를 계속 해야 할 것 같습니다.