백준 16953 자바 풀이

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

16953번: A → B

BFS로 풀어 A가 B로 가는 최단거리를 check 배열을 통해 뎁스로 구하려고 했으나 A, B의 범위가 커서(10의 9제곱) 타임아웃이 날 게 뻔했다. 어떻게 풀면 타임아웃이 안날까 고민하다가 구글링을 했고, 이를 통해 B -> A 과정을 구하면 된다는 힌트를 얻었다.

따라서 BFS 큐에 담아 B가 A가 되도록 구했는데 이렇게 하니 메모리 초과가 났다. 그래서 어떻게 했나 보니..

아예 check 배열을 쓰지 않고 (방문 확인의 의미가 없음) B를 계속해서 나누어 작게 만드는 과정으로만 구현을 한 것이 대부분이었다. 그래서 두번 세번 코드를 갈아 엎고 간단하게 코드를 완성시켰다.

BFS, DFS의 뼈대는 이제 이해가 되는데 이를 간단한 코드로 변경시켜 효율을 내는 것은 아직까진 어려운 듯 하다..

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

public class bj16953 {
    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());

        int cnt = 1;

        while(A != B) {

            if(A > B) {
                System.out.println(-1);
                return;
            }

            if(B % 2 == 0) B /= 2;
            else if(B % 10 == 1) B /= 10;
            else {
                System.out.println(-1);
                return;
            }

            cnt ++;
        }

        System.out.println(cnt);
    }
}