문제

풀이

• DFS, BFS 두 방식 다 제출했는데 비슷한 속도로 통과했다.

코드

• BFS

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

public class Main {

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

        StringTokenizer st=new StringTokenizer(br.readLine());
        String a=st.nextToken();
        long b=Long.parseLong(st.nextToken());
        Queue<Item> q=new LinkedList<>();
        q.add(new Item(a,1));
        int ans=-1;
        while(!q.isEmpty()){
            Item item=q.poll();
            long n=Long.parseLong(item.num);
            if(n==b){
                ans=item.cnt;
                break;
            }
            if(2*n<=b)q.add(new Item(String.valueOf(2*n),item.cnt+1));
            StringBuilder sb=new StringBuilder(item.num);
            sb.append(1);
            if(Long.parseLong(sb.toString())<=b)q.add(new Item(sb.toString(),item.cnt+1));
        }
        System.out.println(ans);
    }

    static class Item{
        String num;
        int cnt;

        public Item(String num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
}

• DFS

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

public class Main {

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

        StringTokenizer st=new StringTokenizer(br.readLine());
        String a=st.nextToken();
        long b=Long.parseLong(st.nextToken());
        Queue<Item> q=new LinkedList<>();
        q.add(new Item(a,1));
        int ans=-1;
        while(!q.isEmpty()){
            Item item=q.poll();
            long n=Long.parseLong(item.num);
            if(n==b){
                ans=item.cnt;
                break;
            }
            if(2*n<=b)q.add(new Item(String.valueOf(2*n),item.cnt+1));
            StringBuilder sb=new StringBuilder(item.num);
            sb.append(1);
            if(Long.parseLong(sb.toString())<=b)q.add(new Item(sb.toString(),item.cnt+1));
        }
        System.out.println(ans);
    }

    static class Item{
        String num;
        int cnt;

        public Item(String num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
}

#dfs #bfs