BOJ - A -> B

https://www.acmicpc.net/problem/16953

16953번: A → B

 

• 그래프 - 너비우선 탐색 문제이다.
• int 형으로 하다가 뒤에 1더하는 조건때문에 고생했는데.. long 으로 바꾸고 10* +1로 계산했다.

 

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


public class Main {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        long A = Integer.parseInt(st.nextToken());
        long B = Integer.parseInt(st.nextToken());

        if(A == B) {
            System.out.println("-1");
            return;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(A, 1));
        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();

            if (currentNode.index == B) {
                System.out.println(currentNode.depth);
                return;
            }

            if (currentNode.index > B) continue;

            queue.offer(new Node(currentNode.index * 2, currentNode.depth + 1));
            queue.offer(new Node(currentNode.index * 10 + 1, currentNode.depth + 1));
        }
        System.out.println("-1");
    }

    static class Node {
        public long index;
        public long depth;

        public Node(long index, long depth) {
            this.index = index;
            this.depth = depth;
        }
    }
}