LeetCode (C/C++, Java) 2059. Minimum Operations to Convert Number

https://leetcode.com/problems/minimum-operations-to-convert-number/description/

---

풀이

모든 수를 탐색하며 3가지 경우의 수를 확인해야 한다.

입력되는 숫자의 범위는 넓지만, 탐색하는 수의 범위는 0 ~ 1000 사이에 있는 값만 사용할 수 있으므로 visited 배열을 이용해 탐색 여부를 확인한다.

이를 queue에 넣어 BFS로 탐색하며 최소 연산 횟수를 찾는다.

---

C/C++ 코드

class Solution {
public:

    int visited[1001];
    queue<int> q;
    int minCnt = INT_MAX;

    // 조건 확인 후 큐에 삽입
    void checkGoalAndMoveNext(long long next, int cnt, int goal) {
        if (0 <= next && next <= 1000) {
            if (visited[next] > cnt + 1) { 
                q.push(next);
                visited[next] = cnt + 1;
            }
        }

        // goal이라면 연산 횟수 계산 후 갱신
        if (next == goal)
            minCnt = min(minCnt, cnt + 1);
    }

    int minimumOperations(vector<int>& nums, int start, int goal) {
        sort(nums.begin(), nums.end());

        fill(visited, visited + 1001, INT_MAX);
        visited[start] = 1;
        q.push(start);

        while (!q.empty()) {
            int now = q.front();
            int cnt = visited[now];
            q.pop();

            // 모든 원소를 돌면서 연산
            for (int n : nums) {
                checkGoalAndMoveNext(now + n, cnt, goal);
                checkGoalAndMoveNext(now - n, cnt, goal);
                checkGoalAndMoveNext(now ^ n, cnt, goal);
            }
        }
        return minCnt == INT_MAX ? -1 : minCnt - 1;
    }
};

 

Java 코드

class Solution {
    public int minimumOperations(int[] nums, int start, int goal) {
        Queue<Integer> q = new ArrayDeque<>();

        boolean[] visited = new boolean[1001];
        int steps = 0;

        visited[start] = true;
        q.add(start);
        while (!q.isEmpty()) {
            int size = q.size();

            // 연산횟수(steps)를 세기 위해 반복문 추가
            while (size-- > 0) {
                int now = q.poll();

                // 모든 문자열을 돌며 세 가지 연산을 수행
                for (int n : nums) {
                    for (int next : new int[]{now + n, now - n, now ^ n}) {

                        // 0 ~ 1000 범위라면 큐에 삽입
                        if (0 <= next && next <= 1000 && !visited[next]) {
                            q.add(next);
                            visited[next] = true;
                        }

                        // goal이라면 현재 스텝 반환
                        if (next == goal) return steps + 1;
                    }
                }
            }

            steps++;
        }
        return -1;
    }
}