[백준]#14395 4연산

문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s s; (출력: )
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

입력

첫째 줄에 s와 t가 주어진다. $(1 ≤ s, t ≤ 10^9)$

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

예제 입력 1

7 392

예제 출력 1

+*+

예제 입력 2

7 256

예제 출력 2

/+***

예제 입력 3

4 256

예제 출력 3

**

예제 입력 4

7 7

예제 출력 4

0

예제 입력 5

7 9

예제 출력 5

-1

예제 입력 5

10 1

예제 출력 5

/

풀이

이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 쉽게 풀 수 있었다. 최대값이 $10^9$ 이기 때문에 중복 체크를 HashSet을 이용했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int start = Integer.parseInt(input[0]);
        int target = Integer.parseInt(input[1]);

        if(start==target) {         //타겟 값과 같은 경우
            System.out.println(0);
            return;
        }

        bfs(start, target);
    }

    public static void bfs(int start, long target) {
        Queue<Pair> queue = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();
        int min_len = Integer.MAX_VALUE;
        String ans = "";
        set.add(start);
        queue.add(new Pair(start, ""));

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            if(temp.num==target) {        //타겟 값에 도달한 경우 최소값 유효성 체크
                if(min_len>=temp.str.length()) {
                    if(min_len==temp.str.length()) {
                        ans = ans.compareTo(temp.str) < 0 ? ans : temp.str;
                    }

                    else {
                        min_len = temp.str.length();
                        ans = temp.str;
                    }
                }
            }

            if(!set.contains(0)) {        //'-'는 무조건 0 이기 때문에 처음에 먼저 계산
                set.add(0);
                queue.add(new Pair(0, "-"));
            }

            if(!set.contains(1)) {      //'/'는 무조건 1 이기 때문에 마찬가지로 먼저 계산
                set.add(1);
                queue.add(new Pair(1, "/"));
            }

            if((long)temp.num*temp.num<=target && !set.contains(temp.num*temp.num)) {       //'*'가 가능한 경우, '*'가 '+'보다 아스키 코드 값이 작기 때문에 먼저 체크
                if(temp.num*temp.num==target)
                    queue.add(new Pair(temp.num*temp.num, temp.str+"*"));

                else {
                    set.add(temp.num*temp.num);
                    queue.add(new Pair(temp.num*temp.num, temp.str+"*"));
                }
            }

            if((long)temp.num+temp.num<=target && !set.contains(temp.num+temp.num)) {     //'+'가 가능한 경우
                if(temp.num+temp.num==target)
                    queue.add(new Pair(temp.num+temp.num, temp.str+"+"));

                else {
                    set.add(temp.num+temp.num);
                    queue.add(new Pair(temp.num+temp.num, temp.str+"+"));
                }
            }
        }

        if(ans.equals(""))          //도달 불가능한 경우
            System.out.println(-1);
        else
            System.out.println(ans);
    }

    public static class Pair {
        int num;
        String str;

        public Pair(int num, String str) {
            this.num = num;
            this.str = str;
        }
    }
}