[백준 16397] 탈출

 

 

일반적인 BFS 탐색에서 조건을 잘 주면 된다.

A 버튼을 눌렀을때는 99999를 넘지않게한다.

B 버튼을 눌러 2배가 되었을때 99999가 넘는다면 그 경우는 통과한다.

 

 

public class Main {
    
    static int t;
    static int g;
    static int max = 100000;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        t = sc.nextInt();
        g = sc.nextInt();
        
        int ans = bfs(n);
        System.out.println(ans == -1 ? "ANG" : ans);
    }
    
    public static int bfs(int n) {
        Queue<Pair> queue = new LinkedList<Pair>();
        boolean visited[] = new boolean[max];
        
        queue.offer(new Pair(n, 0));
        visited[n] = true;
        
        while(!queue.isEmpty()) {
            Pair point = queue.poll();
            if(point.cnt > t) break;
            if(point.n == g) return point.cnt;
            
            int plusOne = point.n + 1;
            if(plusOne < max && !visited[plusOne]) {
                visited[plusOne] = true;
                queue.offer(new Pair(plusOne, point.cnt + 1));
            }
            
            int makeDouble = makeDouble(point.n);
            if(makeDouble >= max) continue;
            
            int minusHeadOne = minusHeadOne(makeDouble);
            if(minusHeadOne < max && !visited[minusHeadOne]) {
                visited[minusHeadOne] = true;
                queue.offer(new Pair(minusHeadOne, point.cnt + 1));
            }
        }
        return -1;
    }
    
    public static int makeDouble(int n) {
        return n * 2;
    }
    
    public static int minusHeadOne(int n) {
        if(n == 0) return 0;
        for(int i=10; true; i*=10) {
            if(i > n) {
                n -= i/10;
                break;
            }
        }
        return n;
    }
    
    static class Pair {
        int n;
        int cnt;
        
        Pair(int n, int cnt) {
            this.n = n;
            this.cnt = cnt;
        }
    }
}