백준 25418번 : 정수 a를 k로 만들기

---

이번 문제는 다음 두 가지 연산을 통해 정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하는 문제이다.

연산 :

1. 정수 A에 1을 더한다.
2. 정수 A에 2를 곱한다.

제한 :
1 ≤ A < K ≤ 1,000,000

이 문제는 이전에 풀었던 A → B 문제와 거의 동일하다.

당시 문제는 1을 더하는 것이 아닌 1을 수의 가장 오른쪽에 추가해야한다는 트릭이 있었기 때문에 이 부분에 대해 조금 생각을 해볼 필요가 있었다.

다만 이번 문제는 연산에서 그러한 트릭이 없기 때문에 단순히 BFS를 통해 연산을 진행하고, 횟수를 찾으면 되지만 신경 써줘야할 다른 문제가 있다.

앞서 풀었던 A → B 문제와 로직이 똑같기 때문에 자세한 설명은 넘어간다.

차이점을 조금 살펴볼 것인데, 바로 전체 소스 코드를 보자.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int a, k;
    static boolean[] visited;

    public static void main(String[] args) throws java.io.IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        a = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        visited = new boolean[k + 1];

        bfs();
    }

    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{a, 0});
        visited[a] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int val = cur[0];
            int count = cur[1];

            if (val == k) {
                System.out.println(count);
                return;
            }

            if (val * 2 <= k) {
                visited[val * 2] = true;
                q.offer(new int[]{val * 2, count + 1});
            }

            if (!visited[val + 1]) {
                q.offer(new int[]{val + 1, count + 1});
            }
        }

        System.out.println(-1);
    }
}

A → B 문제에서는 A에 2를 곱하는 연산말고도 A의 가장 뒤에 1을 추가하는 연산이 있었다.

해당 연산을 진행하면 숫자가 굉장히 커지기 때문에 이전에 방문했던 결과를 재방문하는 경우가 일반적으로 없을 것이다.

그렇기 때문에 해당 문제에서 방문 여부 체크를 하던 안 하던 시간복잡도의 차이가 미미한 수준이다.

다만 공간복잡도는 올라갈 수 있기 때문에 별도로 방문 여부를 체크하는 로직은 작성하지 않았다.

반면에 이번 문제의 경우는 방문 여부를 체크했는데, 이는 공간 복잡도가 올라가겠지만 정상적인 출력을 위해 반드시 필요하다.

앞서 A의 가장 뒤에 1을 추가하는 연산을 하면 재방문할 경우가 거의 없다고 말했는데, 이번에는 상황이 다르다.

2를 곱하는 연산 말고도 1을 더해주는 연산이 진행되기 때문에 숫자가 가까워 재방문할 경우의 수가 굉장히 많다.

그렇기 때문에 이번 문제에서는 동일한 로직이지만 재방문을 피하기 위해 visited 배열을 선언하여 방문 여부를 체크해주고 있다.

            if (val * 2 <= k) {
                visited[val * 2] = true;
                q.offer(new int[]{val * 2, count + 1});
            }

            if (!visited[val + 1]) {
                q.offer(new int[]{val + 1, count + 1});
            }

특히 이 두 가지로 분기된 연산에서 2를 곱한 경우 해당 위치를 true로 변경하였고 그 다음 1을 더하는 연산에서 해당 위치를 방문하지 않도록 조정한다.

이를 통해 재방문을 방지하고 원하는 결과를 출력할 수 있는 것이다.

이 외에도 다익스트라, 그리디, DP 알고리즘으로도 풀 수 있다.

이 블로그에서 다른 풀이를 참고할 수 있다.

전체 소스 코드의 결과는 다음과 같다.

---

설명이 약간 부족한가 싶긴한데, 이전 문제와 이번 문제의 차이에 대한 얘기는 했기 때문에 넘어갔다.

사실 이번 문제가 증가하는 숫자가 작아서 방문 여부를 체크해야한다 정도 알고 있으면 될 것 같고, A → B 문제와 크게 다른 로직이 없어 빠르게 풀었다.

그리고, 다익스트라, 그리디, DP 알고리즘으로 풀어본 결과를 적어야하나 싶기도하다.