백준 16953 (A->B) java

문제

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

16953번: A → B

코드

import java.math.BigInteger;
import java.util.*;
import java.io.*;
public class Main {
    static BigInteger n;
    static BigInteger m ;
    static LinkedList<Integer> count = new LinkedList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        n = new BigInteger(st.nextToken()) ;
        m = new BigInteger(st.nextToken()) ;

        if(n.compareTo(m)==0)
            System.out.println(1);
        else {
            int result = bfs();
            System.out.println(result);
        }
        bf.close();
    }

    static int bfs()
    {
        Queue<BigInteger> q = new LinkedList<>();
        q.add(n);
        count.add(1);

        while(!q.isEmpty())
        {
            BigInteger cur = q.poll();
            int c1 = count.poll();

            BigInteger n1 = cur.multiply(new BigInteger("2"));
            BigInteger n2 = cur.multiply(new BigInteger("10")).add(new BigInteger("1"));
            int cur1 = n1.compareTo(m);
            int cur2 = n2.compareTo(m);

            if(cur1==0||cur2==0)
            {
                return c1+1;
            }
            if(cur1==-1)
            {
                q.add(n1);
                count.add(c1+1);
            }
            if(cur2==-1)
            {
                q.add(n2);
                count.add(c1+1);
            }
        }

        return -1;
    }
}

 

기본적으로 주어지는 n,m의 값이 int 형이나 long형의 범위를 벗어나기 때문에 자바에서는 BigInteger 클래스를 사용하여 풀어야 한다.

해당 클래스의 사칙 연산 함수 같은 경우에는 간간히 사용하기 때문에 익혀두고 있어야 한다.

 

위 문제는 특이하게 visit (방문 정보) 를 처리하지 않아도 된다. 그 이유는 기본적으로 탐색한 정수 값을 다시는 방문하지 않기 때문이다!!!!

1번 이동의 곱하기 2는 짝수, 2번 이동의 곱하기 10 하고 더하기 1은 홀수 -> 값이 겹치는 일이 발생하지 않는다.

그리고 탐색을 진행할수록 값은 커지기만 하기 때문에 탐색한 정수값을 다시 방문하는 일은 없다.