[백준] 16953. A->B

문제 링크

[백준] 16953. A->B

풀이 과정

주어진 규칙에 따라 숫자 A를 B로 바꾸는 데에 몇 번의 최소 연산 과정이 필요한 지를 묻는 BFS 탐색 문제입니다.

long A, B;

A와 B는 최대 $10^9$ 까지 가능하므로, Long 타입으로 선언해주었습니다.

static long bfs() {
        int cnt = 0;
        Queue<Long> q = new LinkedList<>();
        q.add(A);

        while (!q.isEmpty()) {
            int size = q.size();

            for (int s = 0; s < size; s++) {
                long now = q.poll();

                if (now == B) return cnt + 1;

                if (now * 2 <= B) q.add(now * 2);
                if (now * 10 + 1 <= B) q.add(now * 10 + 1);
            }

            cnt++;
        }

        return -1;
    }

규칙에 의해 만들어진 수에 2를 곱하거나, 10을 곱한 후 1을 더하는 과정을 거친 값이 B를 넘어가면 순간 해당 값으로는 BFS 탐색을 종료하게 됩니다. 따라서, 따로 방문 여부를 처리하는 배열이 필요하지 않습니다.

코드

import java.util.*;

public class Main {
    static long A, B;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        A = sc.nextLong();
        B = sc.nextLong();

        System.out.println(bfs());
    }

    static long bfs() {
        int cnt = 0;
        Queue<Long> q = new LinkedList<>();
        q.add(A);

        while (!q.isEmpty()) {
            int size = q.size();

            for (int s = 0; s < size; s++) {
                long now = q.poll();

                if (now == B) return cnt + 1;

                if (now * 2 <= B) q.add(now * 2);
                if (now * 10 + 1 <= B) q.add(now * 10 + 1);
            }

            cnt++;
        }

        return -1;
    }
}