[백준 16953] A → B (Java)

문제

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

풀이

BFS를 이용해 풀었다.
현재 값을 X라고 한다면, X == B 인지 검사한다.
만약 X == B일 경우 그대로 연산 횟수를 리턴하고,
X != B일 경우 2X 값과 10X+1 값을 Queue에 넣고 이를 반복한다.
Queue에 넣을때 일단 연산이 2X과 10X+1밖에 없으므로 다음 값이 줄어들리가 없다. 그러므로 B보다 크면 넣지 않는다.
또한, 한 번 나온 값이면 이 또한 넣지 않는다.

코드

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static class Num{
        long cur;
        int numOfOper;
        public Num(long cur, int numOfOper){
            this.cur = cur;
            this.numOfOper = numOfOper;
        }
    }
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int A = scan.nextInt();
        int B = scan.nextInt();
        System.out.println(solution(A, B));
    }
    public static int solution(int A, int B){
        Queue<Num> Q = new LinkedList();
        Q.add(new Num(A, 1));
        HashSet<Long> set = new HashSet();
        while(!Q.isEmpty()){
            Num curNum = Q.poll();
            long cur = curNum.cur;
            int numOfOper = curNum.numOfOper;
            if(cur == B) return numOfOper;
            if(set.contains(cur)) continue;
            set.add(cur);

            long next = cur*2;
            if(!set.contains(next) && next<=B) Q.add(new Num(next, numOfOper+1));
            next = cur*10+1;
            if(!set.contains(next) && next<=B) Q.add(new Num(next, numOfOper+1));
        }
        return -1;
    }

}```