[백준] 16953 A → B | DFS, BFS, 그래프 | 실버 Ⅱ | JAVA

📌 문제

https://www.acmicpc.net/problem/16953

 

⭐ 풀이 과정

1. 문제 정의:
   • BFS 탐색에서 큐를 이용해 현재 숫자와 연산 횟수를 저장합니다.
   • 큐에서 숫자를 꺼내 가능한 연산(2를 곱하거나, 1을 추가)을 수행한 결과를 큐에 삽입합니다.
   • 연산이 끝난 후 목표 값 B에 도달하면 최소 연산 횟수를 출력합니다.
   • BFS를 종료했는데도 B에 도달하지 못한 경우 -1을 출력합니다.
2. 제약 조건:
   • 숫자가 B를 초과하면 더 이상 탐색할 필요가 없습니다.

 

✅ 정답 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

        System.out.println(bfs(A, B));
    }

    private static int bfs(long A, long B) {
        Queue<long[]> queue = new LinkedList<>();
        queue.offer(new long[]{A, 1}); // 현재 값과 연산 횟수 저장

        while (!queue.isEmpty()) {
            long[] current = queue.poll();
            long currentValue = current[0];
            int steps = (int) current[1];

            // B에 도달한 경우 연산 횟수 반환
            if (currentValue == B) {
                return steps;
            }

            // 다음 가능한 연산 수행
            long next1 = currentValue * 2;
            long next2 = currentValue * 10 + 1;

            // 연산 결과가 B 이하일 때만 큐에 추가
            if (next1 <= B) {
                queue.offer(new long[]{next1, steps + 1});
            }
            if (next2 <= B) {
                queue.offer(new long[]{next2, steps + 1});
            }
        }

        // B에 도달할 수 없는 경우
        return -1;
    }
}

🗒️ 코드 설명

1. 입력 처리: A와 B를 입력받습니다.
2. BFS 탐색:
   • 큐에 초기 값 (A, 1)을 추가합니다. 여기서 1은 첫 번째 연산입니다.
   • 큐에서 값을 꺼내 현재 값이 B인지 확인합니다.
   • 현재 값에서 가능한 연산 (2를 곱하거나, 1을 추가)을 수행하고 결과를 큐에 추가합니다.
   • 연산 결과가 B를 초과하면 더 이상 탐색하지 않습니다.
3. 결과 반환:
   • BFS를 통해 B에 도달하면 연산 횟수를 반환합니다.
   • BFS 탐색이 끝난 후에도 도달하지 못하면 -1을 반환합니다.