숫자 변환하기

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

---

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

---

입출력 예

x y n result

10	40	5	2
10	40	30	1
2	5	4	-1

---

입출력 예 설명

입출력 예 #1

x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2

x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3

x를 y로 변환할 수 없기 때문에 -1을 return합니다.

너비 우선 탐색(BFS)를 사용하여 풀 수 있다. 주어진 연산에 대하여 모든 가능한 결과를 큐에 넣고, 이를 반복하면서 y에 도달할 때까지의 최소 연산 횟수를 찾을 수 있다.

package LV2;

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

public class H154538 {
    public int solution(int x, int y, int n) {
        // 연산 결과 범위를 1_000_001로 설정
        final int MAX = 1_000_001;

        // check 배열은 각 숫자에 도달하기 위한 최소 연산 횟수를 저장
        // 아직 도달하지 못한 숫자는 -1로 초기화하기
        int[] check = new int[MAX];
        for (int i = 0; i < MAX; i++) {
            check[i] = -1;
        }

        // 큐를 생성하고 시작 숫자 x를 넣는다.
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        // x에 대한 연산 횟수를 0으로 설정한다.
        check[x] = 0;

        // 큐가 비어있지 않은 동안 다음을 반복!
        while (!queue.isEmpty()) {
            // 큐에서 숫자를 꺼낸다.
            int current = queue.remove();

            // 꺼낸 숫자가 y와 같다면, 그 때의 연산 횟수를 반환한다.
            if (current == y) {
                return check[current];
            }

            // 꺼낸 숫자에 n을 더하거나, 2를 곱하거나, 3을 곱하여 다음 숫자를 계산한다.
            int[] next = {current + n, current * 2, current * 3};
            for (int i = 0; i < 3; i++) {
                // 다음 숫자가 범위 내에 있고 아직 방문하지 않았다면,
                if (next[i] > 0 && next[i] < MAX && check[next[i]] == -1) {
                    // 큐에 다음 숫자를 넣고 연산 횟수를 업데이트한다.
                    queue.add(next[i]);
                    check[next[i]] = check[current] + 1;
                }
            }
        }

        // 큐가 비어도 y에 도달하지 못했다면, y에 도달할 수 없다는 의미이므로 -1을 반환한다.
        return -1;
    }
}

입력값 범위가 1,000,000 이하라는 것을 이용한다. check 배열은 각 숫자에 도달하기 위한 최소 연산 횟수를 저장하며, 아직 도달하지 못한 숫자는 -1로 초기화한다.

큐에 시작 숫자 x를 넣고, x에 대한 연산 횟수를 0으로 설정한다. 그 후, 큐가 비어있지 않은 동안 다음을 반복한다:

1. 큐에서 숫자를 꺼내온다.
2. 꺼낸 숫자가 y와 같다면, 그 때의 연산 횟수를 반환한다.
3. 꺼낸 숫자에 n을 더하거나, 2를 곱하거나, 3을 곱하여 다음 숫자를 계산한다.
4. 만약 다음 숫자가 범위 내에 있고 아직 방문하지 않았다면, 큐에 다음 숫자를 넣고 연산 횟수를 업데이트한다.

만약 큐가 비어도 y에 도달하지 못했다면, y에 도달할 수 없다는 의미이므로 -1을 반환한다.

https://aihtnyc-h.tistory.com/entry/%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS

너비 우선 탐색(BFS)