[백준/BFS] 16953번 A→B (JAVA)

문제

---

풀이

Result 클래스와 Stack 자료구조를 활용해서 풀이했다. Result 클래스를 따로 만든 이유는 계산 결괏값 value와 연산 횟수 count를 같이 저장하기 위해서다. 아래와 같은 풀이과정을 통해 답을 구할 수 있다.

1. current를 주어진 조건에 따라 계산하여 mul과 add를 구한다.
2. 결괏값이 b와 일치하면 answer를 최솟값으로 갱신한다.
3. 결괏값이 b보다 작으면 count를 증가시켜 Stack에 다시 push한다.

코드

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

public class Main {

    private static final int IMPOSSIBLE = -1;
    private static final int MUL = 2;
    private static final int ADD = 1;

    private static long a;
    private static long b;
    private static int answer = Integer.MAX_VALUE;

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

        parseInput(br);
        countMinOperation();
        bw.append(String.valueOf(answer == Integer.MAX_VALUE ? IMPOSSIBLE : answer + 1));

        br.close();
        bw.close();
    }

    private static void parseInput(BufferedReader br) throws IOException {
        String[] line = br.readLine().split(" ");
        a = Long.parseLong(line[0]);
        b = Long.parseLong(line[1]);
    }

    private static void countMinOperation() {
        Stack<Result> stack = new Stack<>();
        stack.push(new Result(a, 0));
        while (!stack.isEmpty()) {
            Result current = stack.pop();

            long mul = mul(current.value);
            if (mul == b) answer = Math.min(answer, current.count + 1);
            else if (mul < b) stack.push(new Result(mul, current.count + 1));

            long add = add(current.value);
            if (add == b) answer = Math.min(answer, current.count + 1);
            else if (add < b) stack.push(new Result(add, current.count + 1));
        }
    }

    private static long mul(long current) {
        return current * MUL;
    }

    private static long add(long current) {
        return Long.parseLong(current + String.valueOf(ADD));
    }
}

class Result {
    long value;
    int count;

    public Result(long value, int count) {
        this.value = value;
        this.count = count;
    }
}