[백준 16953] A → B (JAVA)

백준 16953번 문제 -  A → B

16953번: A → B

---

문제 분석 

---

 

해결 포인트

 

• BFS 사용
• A부터 큐에 삽입 후, 큐에서 값을 꺼내 [*2, 오른쪽에 1추가] 계산 후 큐에 삽입 
  • 만약 해당 값이 B보다 크면 큐에 삽입하지 않는다.
  • 큐에 추가 전 담겨져 있는 수 만큼 반복, 후 count 증가
• 큐에서 값을 꺼냈을 때 값이 B이면 count 반환

---

 

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        bw.write(BFS(a,b) + "\n");

        bw.flush();
        bw.close();
    }

    public static long BFS(long a, long b) {
        Queue<Long> queue = new LinkedList<>();
        queue.add(a);

        long count = 1;
        while (!queue.isEmpty()) {
            int queueSize = queue.size();

            for (int i = 0; i < queueSize; i++) {
                long value = queue.poll();

                if (value == b) {
                    return count;
                }

                if (value * 2 <= b) {
                    queue.add(value * 2);
                }
                if (value * 10 + 1 <= b) {
                    queue.add(value * 10 + 1);
                }
            }
            count++;
        }

        return -1;
    }
}