[ 백준 ] 1463 1로 만들기

Link | 1463번 문제 : 1로 만들기

Analyze

이 문제는 BFS를 통해 해결할 수 있다.

X 객체에는 현재 숫자와 몇 번의 계산을 하였는지 저장되어 있다.

최초의 X는 초기 x 값과 step = 0을 저장한다.

X들을 Queue에 저장하면서 BFS를 한다.

추가 계산이 가능하다면 각각의 계산 가능성을 판단하여 queue에 추가한다.

만약 queue의 첫 번째 X가 1이 되었다면 해당 X의 step이 최소 계산 횟수이다.

Queue에 저장되는 X의 step은 갈 수록 커지기 때문에 처음으로 찾을 수 있는 x = 1의

step이 최소 step이다.

Solution

private static void solution() throws IOException {
    Queue<X> xs = new LinkedList<>(Collections.singleton(
            new X(Integer.parseInt(reader.readLine()), 0)));
    while (!xs.isEmpty()) {
        X x = xs.poll();
        if (x.x == 1) {
            result.append(x.step);
            break;
        }
        if (x.x % 3 == 0) xs.add(new X(x.x / 3, x.step + 1));
        if (x.x % 2 == 0) xs.add(new X(x.x / 2, x.step + 1));
        xs.add(new X(x.x - 1, x.step + 1));
    }
}

static class X {
    int x, step;

    public X(int x, int step) {
        this.x = x;
        this.step = step;
    }
}