[백준] 16953: A → B JAVA

접근

bfs로 큐에 넣어가며 하나씩 확인하다가 b와 똑같은 수가 나온다면, 이는 필요한 연산의 최솟값이 되기 때문에 바로 그 값을 리턴한다. 만약 큐에서 뽑은 수가 b보다 크다면, 가능한 연산은 모두 현재 수보다 증가하는 것이므로 그냥 넘어가도록 한다. 그렇게 a로 만들 수 있으면서 b보다 작은 모든 수를 확인했는데도 b가 만들어지지 않았다면, 해당 수를 만들 수 없는 경우이기 때문에 -1를 리턴한다.

 

처음에 단순히 A, B의 범위만 봤을 때는 int로 처리가 가능할 것이라 생각했는데, 연산 중에 int 범위를 넘어가면서 오버플로우가 발생하는 경우가 있었다. (9억에 10을 곱하고 1을 더하면 int 최대값인 약 21억을 넘어가게 됨)  

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ16953 {
    static class ConvNum {
        long num; // 오버플로우 방지
        int cnt;

        ConvNum(long num, int cnt){
            this.num = num;
            this.cnt = cnt;
        }
    }

    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());

        System.out.println(bfs(a, b));
    }

    private static int bfs(int a, int b) {
        Queue<ConvNum> q = new LinkedList<>();
        q.add(new ConvNum(a, 0));

        while(!q.isEmpty()){
            ConvNum cur = q.poll();

            if(cur.num == b) return cur.cnt + 1;
            else if(cur.num > b) continue; // 더 큰 수는 연산할 필요가 없음

            q.add(new ConvNum(cur.num*2, cur.cnt+1));
            q.add(new ConvNum(cur.num*10+1, cur.cnt+1));
        }

        return -1; // 만들 수 없는 경우
    }
}