[알고리즘 문제 풀이] 백준 1463 1로 만들기 (BFS/DFS + DP)

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

import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class Main{

    static int N;

    static int[] visited;

    static Queue<Integer> q;

    public static void main(String[] args) throws IOException{

        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st =new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        visited = new int[N+1];

        bfs();
        System.out.println(visited[1]);

    }

    static void bfs(){
        q=new LinkedList<>();
        q.offer(N);
        while(!q.isEmpty()){
            int x = q.poll();
            if(x==1) break;

                if(x%3 == 0 ) {
                    int y= x/3; // y는 새롭게 방문할 지점
                    verified(y,x);
                }
                if ( x%2==0){
                    int y= x/2; // y는 새롭게 방문할 지점
                    verified(y,x);
                }
                int y= x-1;
                verified(y,x);


        }


    }
    public static void verified(int y,int x) {
        if (visited[y] > visited[x] + 1 || visited[y] == 0) {
            visited[y] = visited[x] + 1;
            q.offer(y);
        }
    }
}