[25418] 정수 a를 k로 만들기

🔗 문제 링크

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

🔍 문제 설명

입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

• 연산 1: 정수 A에 1을 더한다.
• 연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

⚠️ 제한사항

• 첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다.

---

🗝 풀이 (언어 : Java)

BFS로 푸는 문제이다. boolean 배열을 하나 더 선언해서, 연산 2에서 이미 큐로 들어간 숫자는 연산 1에서 다시 큐에 넣지 않아야 한다. 이 부분을 놓쳐서 메모리 초과 오류가 났다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        br.close();
        solution(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }

    private static void solution(int A, int K) {
        ArrayDeque<Integer> queue = new ArrayDeque<>() {{
            addLast(A);
        }};
        boolean[] visited = new boolean[K + 1]; //확인한 숫자 기록하는 배열
        visited[A] = true;
        int count = 0; //연산 횟수
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int number = queue.pollFirst();
                if (number == K) { //정답 발견하면 종료
                    System.out.println(count);
                    return;
                }
                //연산 1
                int case1 = number + 1;
                if (case1 <= K && !visited[case1]) { //연산 1에서 큐에 들어간 숫자를 중복해서 넣지 않도록 체크
                    queue.addLast(case1);
                }
                //연산 2
                int case2 = number * 2;
                if (case2 <= K) {
                    queue.addLast(case2);
                    visited[case2] = true; //연산 2에서 큐에 들어간 숫자 기록
                }
            }
            count++;
        }
    }

}