[BOJ] 16953. A → B

문제 원본 : https://www.acmicpc.net/problem/16953

16953번: A → B

import java.io.*;
import java.util.ArrayDeque;
import java.util.Hashtable;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String s = br.readLine();
        long a = Long.parseLong(s.split(" ")[0]);
        long b = Long.parseLong(s.split(" ")[1]);

        Queue<Long> queue = new ArrayDeque<>();
        Hashtable<Long, Integer> hashtable = new Hashtable<>();
        queue.add(b);
        hashtable.put(b, 1);

        while (!queue.isEmpty()) {
            long curr = queue.poll();
            int cnt = hashtable.get(curr);

            if (curr == a) {
                bw.write(String.valueOf(cnt));

                bw.close();
                br.close();
                return;
            }

            if (curr % 2 == 0 && hashtable.get(curr / 2) == null) {
                queue.add(curr / 2);
                hashtable.put(curr / 2, cnt + 1);
            }

            if (curr % 10 == 1 && hashtable.get(curr / 10) == null) {
                queue.add(curr / 10);
                hashtable.put(curr / 10, cnt + 1);
            }
        }

        bw.write(String.valueOf(-1));

        bw.close();
        br.close();
    }
}

• BFS 문제
• 처음에는 정방향으로 했다가 시간 초과가 났다.
• 조건 없이 매번 2배씩 늘어나니 시간 초과가 날 수밖에 없었다.
• 역방향으로 하니 경우의 수가 훨씬 줄어들어 시간 초과를 피할 수 있었다.