BFS

백준 16953번을 BFS를 이용해 Java로 풀어봤다. 생각보다 간단한 문제 같았고 실제로 금방 코드를 완성해 제출했지만 계속해서 틀렸다는 결과를 받았다. Intelli J에서 혼자 입력값을 넣었을 때는 잘 나왔는데 왜 자꾸 틀린 건지 도저히 감이 잡히지 않았다.

결국 다른 분들의 풀이를 참고해봤는데 변수의 type이 int가 아닌 long이어야 하는 것을 잡아내지 못했다. 아직까지 알고리즘 공부를 많이 하지 않아서 언제 어떤 알고리즘을 써야 하며, input 값들의 범위에 따라 적절한 type을 잡는 것도 미숙하다.

주어진 입력값의 범위는 분명 20억을 넘지 않는데 어째서 long을 써야하는지를 혼자 잠시 고민해봤다.

왜 long 을 써야 하는가?

만약 5억을 10억으로 만들 경우에는, 두 가지 종류의 연산 중 마지막 자리에 1을 붙이는 연산을 진행할 경우에 Queue 에 50억+1 이 들어가야 하므로 overflow가 발생하게 된다!
그래서 int가 아닌 long을 사용해야 하는 거였다.

아래는 내가 제출한 코드다.

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

public class boj16953 {
    static long a,b;
    static int cnt;

    static int bfs(){
        Queue<Long> q = new LinkedList<>();
        q.add(a);

        while(!q.isEmpty()){
            int size = q.size();

            for(int i=0; i<size; i++){
                long tmp = q.poll();
                if(tmp==b)
                    return cnt+1;

                if(tmp*2<=b) q.add(tmp*2);
                if(tmp*10+1<=b) q.add(tmp*10+1);
            }
            cnt++;
        }
        return -1;
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());

        a = Long.parseLong(stk.nextToken());
        b = Long.parseLong(stk.nextToken());

        System.out.println(bfs());
    }
}