[백준 16953] A->B

백준 16953 A -> B

접근

• 처음에는 이진 트리로 1차원 배열에 두 연산을 저장하면서 진행하려고 했으나 메모리 초과가 발생한다는 것을 깨닫고 방향을 전환하였다.
• BFS 를 통해서 B까지 도달할 수 있는 가능한 연산 횟숫를 찾고자 하였다.
• 만약 가능한 연산이 없을 경우에는 -1을 출력해야 한다.

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        Queue<long[]> queue = new LinkedList<>();
        queue.add(new long[] { A, 1 }); 

        while (!queue.isEmpty()) {
            long[] current = queue.poll();
            long value = current[0];
            long operations = current[1];

            if (value == B) {
                System.out.println(operations);
                return;
            }

            if (value * 2 <= B) {
                queue.add(new long[] { value * 2, operations + 1 });
            }

            if (value * 10 + 1 <= B) {
                queue.add(new long[] { value * 10 + 1, operations + 1 });
            }
        }
        System.out.println(-1);
    }

}