백준 16953번 : A → B java

이 문제는 bfs를 이용하여 A가 조건에 맞게 바뀔 때 B로 가장 적은 연산으로 바뀌는 연산의 수를 구하는 문제입니다.

바로 코드를 보여드리겠습니다.

---

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

public class Main{
    static int B;
    static boolean get;

    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());
        B = Integer.parseInt(st.nextToken());

        int cnt = bfs(A);

        if(get)
            System.out.println(cnt);
        else
            System.out.println(-1);
    }

    static int bfs(int start){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(start, 0));
        Node a = q.peek();

        while(!q.isEmpty()){
            a = q.poll();

            if(a.a == B){
                get = true;
                break;
            }

            if((long)a.a*2<=B)
                q.offer(new Node(a.a*2, a.cnt+1));
            if((long)a.a*10+1<=B)
                q.offer(new Node(a.a*10+1, a.cnt+1));

        }

        return a.cnt+1;
    }
}
class Node{
    int a, cnt;

    Node(int a, int cnt){
        this.a = a;
        this.cnt = cnt;
    }
}

이 문제를 풀 때 유의하셔야 되는 점은 아래의 코드입니다.

if((long)a.a*2<=B)
    q.offer(new Node(a.a*2, a.cnt+1));
if((long)a.a*10+1<=B)
    q.offer(new Node(a.a*10+1, a.cnt+1));

java에서는 정수의 기본형이 int입니다. 인트는 2^31 - 1 즉 2,147,483,647까지 표현이 가능합니다.

이 문제에서 A와 B의 범위는(1 ≤ A < B ≤ 10^9)입니다.

10^9의 값은 1,000,000,000이고 A가 10^9-1의 값이라고 할 때 a*10+1을 하면 int의 값을 넘어버립니다.

따라서 long으로 캐스팅을 해주어야 올바른 정답을 도출할 수 있습니다.