사진을 클릭하면 문제로 이동합니다.

📋문제 정리

• a를 연산 1을 하거나 연산 2를해서 k로 만들기 위한 최소 연산 횟수를 구해라

🎯풀이

• queue<int [ ]>를 이용한 bfs 풀이 [0] = 연산한 값 / [1] = 연산 단계

• queue가 비어있지 않으면 removeFirst로 숫자 가져옴

• 숫자가 k보다 크지않고 방문하지 않았다면 과정 진행

• k랑 같다면 [1] 출력 후 종료

• k랑 같지않다면 연산 1 , 연산 2 수행 후 각각 queue에 addLast / 반복

import java.util.*;
import java.io.*;

public class Main{

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[k+1];

        queue.addLast(new int[] {a,0});

        while(!queue.isEmpty()){
            int arr[] = queue.removeFirst();

            if (arr[0] >= visited.length || visited[arr[0]]) continue;
            
            visited[arr[0]] = true;

            if(arr[0] == k){
                sb.append(arr[1]);
                break;
            }

            queue.addLast(new int[] {arr[0]+1,arr[1]+1});
            queue.addLast(new int[] {arr[0]*2,arr[1]+1});

        }

        System.out.print(sb);
        br.close();
    }
}