#백준_16593 A → B - Java 자바

#유형 : 그래프 탐색, BFS

#난이도 : 골드 V

# 맨처음엔 그냥 boolean 형 배열로 통해 접근하려했으나, 10^9 값때문에 메모리 초과가 발생했다. 따라서 HashMap 자료구조를 활용하여 접근하여 해결하였다. 이 때 val 접근을 int 로 하면 끝에 1을 붙이는 연산으로 자료형 오류가 발생, 즉 런타임오류가 발생한다. 따라서 long 타입으로 접근하여 해결하면 된다.

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p16953 {
    static int A,B;
    static HashMap<Long, Integer> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=  new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        int val = bfs();
        if(val == -1)
            System.out.println(val);
        else
            System.out.println(val+1);
        
    }
    public static int bfs() {
        
        Queue<Po> queue = new LinkedList<Po>();
        queue.add(new Po(A,0));
        while(!queue.isEmpty()) {
            Po p = queue.poll();
//            System.out.println(po.x + " " +po.y);
            if(p.val == B) {
                return p.cnt;
            }
            if(p.val * 2 <= B && !map.containsKey(p.val*2)) {
                map.put(p.val*2, p.cnt+1);
                queue.add(new Po(p.val*2, p.cnt+1));
            }
            if(p.val*10 + 1 <= B && !map.containsKey(p.val*10 +1)) {
                map.put(p.val*10 + 1, p.cnt+1);
                queue.add(new Po(p.val*10 + 1, p.cnt+1));
            }
        }
    
        return -1;
    }
    public static class Po{
        long val;
        int cnt;
        public Po(long v, int c) {
            this.val=v;
            this.cnt=c;
        }
    }
}