[코드트리] 4가지 연산을 이용하여 1 만들기

문제링크

문제

n이 주어지고 4가지 연산을 사용하여 1을 만들 수 있는 연산의 최소 수를 구하라

문제 풀이

• 4가지 방법을 모두 사용해봐야함 -> 4군데를 도는 bfs라고 생각
• 지나간 곳을 지나가지 않도록 하는 visited 필요 -> 범위 설정에 어려움
  -> boolean[] visited 대신에 Set<Integer> set를 사용하자

풀이 코드

import java.util.*;

public class Main {
    public static int n;
    public static Queue<int[]> q = new LinkedList<>();
    public static Set<Integer> set = new HashSet<>();

    public static int calculation(int idx, int n){
        if (idx == 0)
            return n - 1;
        else if (idx == 1)
            return n + 1;
        else if (idx == 2 && n % 2 == 0)
            return n / 2;
        else if (idx == 3 && n % 3 == 0)
            return n / 3;
        return n;
    }

    public static int bfs(){
        while (!q.isEmpty()){
            int[] tmp = q.poll();
            int x = tmp[0];
            int move = tmp[1];

            if (x == 1)
                return move;
            
            for (int i = 0; i < 4; i++){
                int nx = calculation(i, x);
                if (nx == n || set.contains(nx))
                    continue;
                set.add(nx);
                q.add(new int[]{nx, move + 1});
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        q.add(new int[]{n, 0});
        set.add(n);
        System.out.print(bfs());
        
    }
}