[백준] 16953번. A -> B(JAVA)

문제

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

---

풀이

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

public class Main {

    static long a, b; // 범위가 10^9이기에 long 으로 받음
    static int cnt = Integer.MAX_VALUE; // 최솟값을 찾기 위함이므로 제일 큰 값으로 저장

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

        st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        dfs(b, 0);

        if(cnt == Integer.MAX_VALUE){ // 만약 cnt값이 한번이라도 바뀐 적이 없다면.
            System.out.println(-1);
            return;
        }
        System.out.println(cnt + 1);
    }

    private static void dfs(long n, int depth){
        if(n == 0){ // 나누다가 0이 되면 무한 루프에 빠지는 것을 방지하기 위함
            return;
        }
        if(n == a){ // A -> B가 아닌 B -> A의 경우의 수를 찾기 위함
            if(depth < cnt) { // 만약 최솟값이라면 저장
                cnt = depth;
            }
            return;
        }

        if(n % 10 == 1){ // 끝자리가 1이다. 즉, 이 전의 숫자 오른쪽 끝에 1을 추가했을 수 있다.
            dfs(n/10, depth +1);
        }
        if(n % 2 ==0){ // x2를 했을 수 있다.
            dfs(n / 2, depth + 1);
        }
        return;

    }


}

 

dfs를 이용할줄 안다면 문제 자체가 어렵지는 않은것 같다.

다만 항상 중요한 것이 A -> B이면 B -> A가 편하지는 않은지, 그리고 그렇게 구한다고 하면 답은 맞게 나오는지를 주의해서 봐야한다는 것이다.