[백준] 16397번 : 탈출

16397번: 탈출

---

[BFS]

문제에서 주어진 B 버튼을 눌렀을 때의 기능을 잘 구현할 수 있다면 어렵지않게 해결할 수 있을 문제. B는 n을 2배로 증가하고 0이 아닌 가장 높은 자릿수의 값을 1 감소시키는 기능이므로 2번의 반복문을 사용하여 해결하였다.

    static int B(int x){

        int result = 0, idx = 10;
        int[] arr = new int[5];

        for(int i=0, k=10000; i<5; i++, k /= 10) { //각 자리수 별 값을 배열에 저장
            arr[i] = (x / k) % 10;

            if(arr[i] != 0)
                idx = Math.min(idx, i);
        }

        arr[idx]--;

        for(int i=0, k=10000; i<5; i++, k/=10) //배열의 값을 5자리수의 숫자로 만듬
            result += arr[i] * k;

        return result;
    }
    //result : 결과값을 반환할 변수
    //idx : 0이 아닌 가장 높은 자릿수를 가질 인덱스

주의해야할 점은 버튼 클릭 수가 T번을 넘으면 안된다는것, 99999를 넘기면 즉, 100000이상이면 실패한다는 것이다.

# Code </>

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

public class Main {

    static int t, g;
    static boolean[] visit = new boolean[100000];
    static int[] click = new int[100000];

    static int B(int x){

        int result = 0, idx = 10;
        int[] arr = new int[5];

        for(int i=0, k=10000; i<5; i++, k /= 10) {
            arr[i] = (x / k) % 10;

            if(arr[i] != 0)
                idx = Math.min(idx, i);
        }

        arr[idx]--;

        for(int i=0, k=10000; i<5; i++, k/=10)
            result += arr[i] * k;

        return result;
    }

    static int BFS(int n){

        int result = -1;
        Queue<Integer> Q = new LinkedList<>();
        visit[n] = true;
        Q.add(n);

        while(!Q.isEmpty()){
            int cur = Q.poll();

            if(cur == g)
                result = click[cur];

            if(click[cur] + 1 > t) continue;

            int a = cur + 1;
            if(a < 100000 && !visit[a]){
                visit[a] = true;
                click[a] = click[cur] + 1;
                Q.add(a);
            }

            int b = cur * 2;

            if(b > 0 && b < 100000){
                b = B(b);
                if(!visit[b]) {
                    visit[b] = true;
                    click[b] = click[cur] + 1;
                    Q.add(b);
                }
            }
        }
        return result;
    }

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

        int n = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        g = Integer.parseInt(st.nextToken());

        int res = BFS(n);
        System.out.println(res != -1? res : "ANG");
    }
}